Competitions » Main CodeFu Competitons » CodeFu 2023 » Qualification Results

Qualification Results

These are the final qualification results.
The first 32 competitors will qualify for the finals.
In case of non eligible competitors or competitors who can't compete in the finals, the following competitors (from 33th position onwards) will take their place in the finals.

micho's solution for 500: City Connector, written in C++, submitted on 07.05.2023 14:13:34


#include <string>

#include <vector>

#include <queue>

#include <set>

#include <stack>

using namespace std;



class CityConnector {

   public:

#define ll long long



    vector<vector<int>> adj;

    vector<int> scc, in, low;

    stack<int> s;

    vector<bool> inStack;

    int scc_num = 0, timer = 0;



    void dfs(int n) {

        low[n] = in[n] = timer++;

        s.push(n);

        inStack[n] = true;

        for (int m : adj[n]) {

            if (in[m] == -1) {

                dfs(m);

                low[n] = min(low[n], low[m]);

            } else if (inStack[m]) {

                low[n] = min(low[n], in[m]);

            }

        }



        if (low[n] == in[n]) {

            while (true) {

                int u = s.top();

                s.pop();

                scc[u] = scc_num;

                inStack[u] = false;

                if (u == n) break;

            }

            ++scc_num;

        }

    }



    // In the scc vector are

    // the IDs of the components for each node

    void run() {

        timer = 0;

        int N = adj.size();

        scc.clear();

        scc.resize(N, -1);

        in.clear();

        in.resize(N, -1);

        low.clear();

        low.resize(N, 0);

        inStack.clear();

        inStack.resize(N, false);

        for (int i = 0; i < N; i++)

            if (scc[i] == -1) dfs(i);

    }

    

    vector<set<int>> g2;

    vector<int> order;

    vector<bool> v2;



    void topo(int u) {

        v2[u] = 1;

        for (auto v: g2[u]) {

            if (v2[v]) continue;

            topo(v);

        }

        order.push_back(u);

    }



    int expandCity(int N, int M, vector<int> SU, vector<int> SV) {

        adj.clear();

        adj.resize(N);

        ll seed_0_u = ((ll)SU[1] * SU[0] + SU[2]) % SU[3];

        ll seed_0_v = ((ll)SV[1] * SV[0] + SV[2]) % SV[3];

        for (int i = 0; i < M; i++) {

            int u = seed_0_u % N;

            int v = seed_0_v % N;

            adj[u].push_back(v);

            seed_0_u = ((ll)SU[1] * seed_0_u + SU[2]) % SU[3];

            seed_0_v = ((ll)SV[1] * seed_0_v + SV[2]) % SV[3];



            // cout << u << " " << v << endl;

        }



        run();



        // for(auto el: scc) cout << el << " ";

        // cout << endl;

        

        g2.clear();

        g2.resize(scc_num + 10);

        for (int i = 0; i < N; i++) {

            for (auto v: adj[i]) {

                if (v == i) continue;

                if (scc[i] == scc[v]) continue;

                g2[scc[i]].insert(scc[v]);

            }

        }



        // cout << "here" << endl;

        // for (auto el: g2) {

        //     for (auto eel: el) cout << eel <<" ";

        //     cout << endl;

        // }

        // cout << "here" << endl;



        vector<int> dp(scc_num + 10, 1);

        // queue<int> q;

        // int ans = 1;

        // for (int i = 0; i < g2.size(); i++) {

        //     if (indeg[i] == 0) {

        //         dp[i] = 1;

        //         q.push(i);

        //     }

        // }



        v2.clear();

        v2.resize(scc_num + 10);

        for (int i = 0; i < g2.size(); i++) {

            if (!v2[i]) topo(i);

        }



        // for (auto el: order) cout << el << " ";

        // cout << endl;



        int ans = 1;

        for (int i = 0; i < order.size(); i++) {

            int u = order[i];

            for (auto v: g2[u]) {

                if (v == u) continue;

                dp[u] = max(dp[u], dp[v] + 1);

                ans = max(ans, dp[u]);

            }

        }

        // for (auto el: dp) cout << el << " ";

        // cout << endl;



        return scc_num - (ans - 1);

    }

};

Test cases result

#	Test Case input	Expected	Received	Status
1.	701, 2802, {23250,30412,7350,1371200953} , {28724,56221,57530,1945258832}	24	24	Correct
2.	5171, 26369, {23528,54377,36419,59366781 9}, {45625,40752,9561,633430904}	61	61	Correct
3.	2213, 10393, {40294,38537,60488,50170457 9}, {47436,31838,44394,634851394}	41	41	Correct
4.	1063, 4458, {56008,40141,59354,876476667 }, {6565,62504,54412,1297355029}	28	28	Correct
5.	4013, 19254, {61107,37143,45879,42837879 8}, {43163,59202,26971,1512117396}	51	51	Correct
6.	4561, 22802, {60940,15614,2125,102209822 0}, {21211,19898,20735,1730809471}	60	60	Correct
7.	2437, 11435, {60105,63870,31092,15401842 54}, {7818,32529,41858,822494267}	41	41	Correct
8.	3989, 19918, {28645,7549,59317,724932182 }, {36762,32536,41537,812912559}	51	51	Correct
9.	2707, 12974, {58329,17351,14934,10502457 21}, {8737,55999,30922,581692873}	44	44	Correct
10.	3943, 18918, {40095,53283,24391,14835472 92}, {40172,62782,21402,1210137185}	54	54	Correct
11.	2999, 14968, {1355,36213,61233,948250571 }, {18419,61706,4957,1163988043}	51	51	Correct
12.	5197, 25445, {51798,12071,57003,45029924 7}, {45808,44274,65283,682554181}	69	69	Correct
13.	1033, 4435, {34499,9919,33460,1530505374 }, {45085,15793,25850,1082321990}	27	27	Correct
14.	43, 106, {54735,27899,27115,971162752}, {28726,970,11303,1502150875}	3	3	Correct
15.	3881, 19014, {32953,38722,32349,14892696 48}, {3794,42473,35968,1390620508}	55	55	Correct
16.	5693, 27318, {44939,28320,8810,90131057} , {64231,26699,31450,822871068}	68	68	Correct
17.	5051, 25757, {40149,13547,30877,43715109 6}, {55656,44321,59335,588202205}	65	65	Correct
18.	1657, 7604, {674,37856,37537,1850892378} , {9515,25239,34477,1717147641}	36	36	Correct
19.	5081, 25910, {49918,35771,54654,17313688 05}, {22732,6654,24159,666842253}	65	65	Correct
20.	2657, 12999, {59622,10053,31976,45843206 7}, {52208,47355,53505,1109507855}	47	47	Correct
21.	5867, 28728, {40695,33279,38722,86338678 2}, {54858,46657,23812,1774336487}	72	72	Correct
22.	2309, 11058, {27127,38073,27778,15786747 02}, {38539,39650,9681,491415520}	41	41	Correct
23.	2693, 13187, {43183,17233,43778,84287536 4}, {8328,8701,20936,1823720233}	47	47	Correct
24.	3671, 18719, {18293,17918,28775,34339101 7}, {23856,37120,21949,1548167507}	51	51	Correct
25.	307, 1124, {1440,61093,29771,793167112}, {15930,6685,42604,1961111792}	12	12	Correct
26.	997, 4370, {41268,16889,25839,913619708} , {53187,5160,10016,1035223157}	24	24	Correct
27.	2347, 10778, {60503,27535,40918,67801576 7}, {46278,8195,2786,1894656122}	44	44	Correct
28.	3187, 16232, {10447,60953,54225,12839989 15}, {62499,14273,51068,1633452528}	46	46	Correct
29.	2741, 13154, {60168,59366,29494,82694775 7}, {22525,6969,40961,69979072}	43	43	Correct
30.	1583, 6958, {23243,14743,52997,666780709 }, {1619,25519,42023,168706311}	32	32	Correct
31.	1483, 6370, {19025,36391,15028,114196879 7}, {13512,34161,29040,1016185778}	32	32	Correct
32.	5741, 28128, {30292,26040,43627,82228007 1}, {16041,56959,40391,1200911006}	70	70	Correct
33.	1373, 6445, {3827,8971,64401,1400973878} , {56654,42362,59265,720400982}	30	30	Correct
34.	5507, 27514, {20656,23794,31303,62742688 6}, {44658,31329,27296,282741451}	70	70	Correct
35.	709, 2818, {17799,4085,12536,1966622666} , {4623,26618,20470,1368856049}	23	23	Correct
36.	5861, 29888, {5009,3995,25146,1857210821 }, {35026,49958,27312,1083979788}	71	71	Correct
37.	373, 1523, {39707,12223,50475,1559723943 }, {50871,60002,4003,219848524}	14	14	Correct
38.	4801, 23522, {30724,20085,30351,15039952 67}, {8886,3575,7263,1948963245}	64	64	Correct
39.	3253, 15281, {44638,33548,59139,37977510 0}, {9133,209,34374,673442663}	53	53	Correct
40.	3923, 18822, {1758,30463,34753,124644347 1}, {59728,37004,57471,396098371}	52	52	Correct
41.	2861, 13730, {24544,62832,36183,63891516 4}, {21434,61725,40379,1816992661}	46	47	Wrong
42.	4783, 23428, {61028,54618,56988,67689951 }, {19042,44560,14319,2128352154}	60	60	Correct
43.	1097, 4701, {51123,45015,13892,181843891 9}, {32201,29804,48337,569458898}	28	28	Correct
44.	199, 740, {14599,28054,30171,413354736}, {57142,53948,12497,1871887008}	10	10	Correct
45.	4813, 23575, {2233,18194,29704,122185610 9}, {1440,46948,64031,1120975776}	65	65	Correct
46.	2903, 14796, {24889,43525,1704,874093101 }, {61907,10933,11295,87302768}	46	40	Wrong
47.	349, 1344, {39054,1219,23803,684406491}, {47882,2559,49204,72225128}	13	12	Wrong
48.	4177, 21281, {31351,24142,26978,26532542 3}, {23838,16915,19642,285938954}	54	51	Wrong
49.	3677, 18731, {24723,12037,35376,32237317 6}, {47670,48694,23183,2026169411}	54	52	Wrong
50.	3593, 17238, {43568,49066,53868,20398411 48}, {44587,26333,61301,252606482}	53	47	Wrong
51.	5581, 27902, {11401,59205,11756,30869960 7}, {1995,58865,753,1468943962}	60	54	Wrong
52.	3001, 14702, {25740,3325,61469,509245679 }, {21878,50969,36488,1900808989}	44	41	Wrong
53.	739, 3230, {29481,4864,57617,979590846}, {56586,48623,41790,833960464}	21	21	Correct
54.	4793, 24435, {21595,38906,12934,15848649 71}, {50966,21537,26126,1274308094}	64	58	Wrong
55.	677, 2895, {52577,23968,55660,2133636231 }, {21345,23670,22311,1629299813}	18	17	Wrong
56.	149, 606, {59791,7737,53988,1704972313}, {39902,31958,49692,1200139206}	7	5	Wrong
57.	4027, 19712, {22500,41846,60762,20564794 06}, {26692,34111,17906,816609933}	58	55	Wrong
58.	3169, 16134, {47078,53719,2008,185535053 0}, {19459,39051,13285,271564691}	46	42	Wrong
59.	103, 356, {63396,35654,25112,442839843}, {24207,34730,46620,1379428914}	4	5	Wrong
60.	1747, 8018, {64349,44426,37203,153517145 0}, {5117,34611,50839,1814123292}	34	33	Wrong
61.	4799, 23968, {60676,304,33681,447174295} , {20899,63253,22345,1781552034}	62	58	Wrong
62.	4703, 23506, {335,20865,1388,101283074}, {33977,11239,64251,1092172620}	58	48	Wrong
63.	1621, 7616, {53691,12574,61210,150081538 6}, {63875,59025,50293,1023802839}	34	32	Wrong
64.	1549, 6794, {23484,1086,12301,1050078579 }, {46763,3991,4079,46512064}	30	32	Wrong
65.	4201, 21422, {63475,1490,14322,700479830 }, {7682,35180,50132,744081989}	57	57	Correct
66.	1153, 5181, {7324,57260,4068,267851505}, {18238,24030,18529,1575686549}	27	28	Wrong
67.	421, 1598, {53573,21470,17803,432455644} , {34772,50649,63478,727687663}	13	14	Wrong
68.	34, 33, {0,1,1,68}, {3,1,2,68}	19	19	Correct
69.	50, 49, {0,1,1,100}, {3,1,2,100}	27	27	Correct
70.	60, 59, {0,1,1,120}, {3,1,2,120}	48	48	Correct
71.	33, 32, {0,1,1,66}, {3,1,2,66}	5	5	Correct
72.	68, 67, {0,1,1,136}, {3,1,2,136}	52	52	Correct
73.	29, 28, {0,1,1,58}, {3,1,2,58}	2	2	Correct
74.	35, 34, {0,1,1,70}, {3,1,2,70}	6	6	Correct
75.	54, 53, {0,1,1,108}, {3,1,2,108}	30	30	Correct
76.	23, 22, {0,1,1,46}, {3,1,2,46}	3	3	Correct
77.	58, 57, {0,1,1,116}, {3,1,2,116}	30	30	Correct
78.	52, 51, {0,1,1,104}, {3,1,2,104}	39	39	Correct
79.	31, 30, {0,1,1,62}, {3,1,2,62}	7	7	Correct
80.	619, 2702, {46859,13703,22861,1762779236 }, {28563,33725,17042,776065396}	20	20	Correct
81.	4, 6, {8718,2597,52637,1179897011}, {379 29,7713,29088,1117485611}	1	1	Correct
82.	4, 3, {58365,4180,41167,1568895621}, {18 278,41689,14091,583269780}	2	2	Correct
83.	1583, 6958, {52488,46676,8125,536091155} , {51996,18992,32534,927171131}	33	33	Correct
84.	809, 3458, {340,53331,4969,429850568}, { 38592,22138,23782,1391547605}	23	23	Correct
85.	3943, 19312, {23400,9993,34284,710318413 }, {16942,32984,35474,1529568368}	53	53	Correct
86.	1913, 9365, {29378,46395,42096,312708465 }, {56434,38076,15353,1453677070}	35	30	Wrong
87.	103, 346, {63396,35654,25112,442839843}, {24207,34730,46620,1379428914}	4	5	Wrong
88.	63, 62, {0,1,1,63}, {2,1,2,63}	13	13	Correct
89.	61, 60, {0,1,1,61}, {2,1,2,61}	2	2	Correct
90.	51, 50, {0,1,1,51}, {2,1,2,51}	8	8	Correct
91.	55, 54, {0,1,1,55}, {2,1,2,55}	5	5	Correct
92.	13, 12, {0,1,1,13}, {2,1,2,13}	2	2	Correct
93.	67, 66, {0,1,1,67}, {2,1,2,67}	2	2	Correct
94.	15, 14, {0,1,1,15}, {2,1,2,15}	5	5	Correct
95.	45, 44, {0,1,1,45}, {2,1,2,45}	8	8	Correct
96.	19, 18, {0,1,1,19}, {2,1,2,19}	2	2	Correct
97.	37, 36, {0,1,1,37}, {2,1,2,37}	2	2	Correct
98.	4253, 21256, {15523,443,24184,1417604697 }, {23330,60438,33320,1532423938}	56	56	Correct
99.	2909, 13358, {47825,13363,3911,373025094 }, {50500,19599,63305,1648971916}	49	49	Correct
100.	349, 1378, {40367,22478,29509,1174273089 }, {28468,38137,6213,830444482}	15	15	Correct