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.

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

#include <string>
#include <vector>
#include <stack>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = 6006;
class CityConnector
{
  public:
    
    vector<int> graph[maxn], rev_graph[maxn];
    bool visited[maxn];
    stack<int> st;
    void top_sort(int node) {
        visited[node] = true;
        for(int i = 0; i < (int) graph[node].size(); i++) {
            int neigh = graph[node][i];
            if(!visited[neigh]) {
                top_sort(neigh);
            }
        }
        st.push(node);
    }
    vector<int> pp;
    void dfs(int node) {
        visited[node] = true;
        pp.push_back(node);
//        cout << node << " ";
        for(int neigh : rev_graph[node]) {
            if(!visited[neigh]) {
                dfs(neigh);
            }
        }
    }
    ll expandCity( ll stations, ll routes, vector<int> sourceGenerator, vector<int> destinationGenerator )
    {
        map<pair<int, int>, bool> mapa;
        vector<pair<ll, ll> > v;
        vector<int> in(stations, 0), out(stations, 0);

        ll seed_0_F = (ll) ((ll)sourceGenerator[1] * (ll)sourceGenerator[0] + (ll)sourceGenerator[2]) % (ll)sourceGenerator[3];
        ll seed_0_T = (ll)((ll)destinationGenerator[1] * (ll)destinationGenerator[0] + (ll)destinationGenerator[2]) % (ll)destinationGenerator[3];
        v.push_back(make_pair(seed_0_F % stations, seed_0_T % stations));
        int A = seed_0_F % stations;
        int B = seed_0_T % stations;
        in[B]++;
        out[A]++;
        graph[A].push_back(B);
        rev_graph[B].push_back(A);
        for(int i = 1; i < routes; i++) {
            ll seed_n_f = (ll) ((ll)sourceGenerator[1] * (ll)seed_0_F + (ll)sourceGenerator[2]) % (ll)sourceGenerator[3];
            
            seed_0_F = seed_n_f;
            ll seed_n_T = (ll)((ll)destinationGenerator[1] * (ll)seed_0_T + (ll)destinationGenerator[2]) % (ll)destinationGenerator[3];
            seed_0_T = seed_n_T;
            
             A = (int) (seed_n_f % stations);
             B = (int) (seed_n_T % stations);
            
            graph[A].push_back(B);
            rev_graph[B].push_back(A);
            in[B]++;
            out[A]++;
//            cout << A << " " << B << endl;
            mapa[{A, B}] = true;
        }
        
        memset(visited, false, sizeof visited);
        for(int i = 0; i < stations; i++) {
            if(!visited[i]) {
                top_sort(i);
            }
        }
        memset(visited, false, sizeof visited);
        vector<int> scc;
        int res = 2e9;
        while(!st.empty()) {
            int p = st.top();
            st.pop();
            if(!visited[p]) {
                pp.clear();
                dfs(p);
                int mm = 0;
                int naj = p;
                for(int x : pp) {
                    if(out[x] + in[x] > mm) {
                        mm = out[x] + in[x];
                        naj = x;
                    }
                }
                scc.push_back(naj);
//                cout << endl;
                
            }
            
        }
        
        for(int i = 0; i < (int) scc.size(); i++) {
//            cout << scc[i] << " ";
            for(int j = 0; j < scc.size(); j++) {
                if(i == j) continue;
                
                graph[scc[i]].push_back(scc[j]);
                rev_graph[scc[j]].push_back(scc[i]);
                int tmp = 0;
                while(!st.empty()) {
                    st.pop();
                }
                memset(visited, false, sizeof visited);
                for(int i = 0; i < stations; i++) {
                    if(!visited[i]) {
                        top_sort(i);
                    }
                }
                memset(visited, false, sizeof visited);
                while(!st.empty()) {
                    int p = st.top();
                    st.pop();
                    if(!visited[p]) {
                        dfs(p);
                        tmp++;
                        
                    }
                    
                }
                res = min(res, tmp);
                graph[scc[i]].pop_back();
                rev_graph[scc[j]].pop_back();
            }
        }
        return res;
    }
};

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		Timeout
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		Timeout
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		Timeout
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		Timeout
17.	5051, 25757, {40149,13547,30877,43715109 6}, {55656,44321,59335,588202205}	65		Timeout
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		Timeout
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		Timeout
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		Timeout
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		Timeout
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		Timeout
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		Timeout
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	46	Correct
42.	4783, 23428, {61028,54618,56988,67689951 }, {19042,44560,14319,2128352154}	60		Timeout
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		Timeout
46.	2903, 14796, {24889,43525,1704,874093101 }, {61907,10933,11295,87302768}	46	39	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	50	Wrong
49.	3677, 18731, {24723,12037,35376,32237317 6}, {47670,48694,23183,2026169411}	54	51	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		Timeout
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	20	Wrong
54.	4793, 24435, {21595,38906,12934,15848649 71}, {50966,21537,26126,1274308094}	64		Timeout
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	4	Correct
60.	1747, 8018, {64349,44426,37203,153517145 0}, {5117,34611,50839,1814123292}	34	32	Wrong
61.	4799, 23968, {60676,304,33681,447174295} , {20899,63253,22345,1781552034}	62		Timeout
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	31	Wrong
64.	1549, 6794, {23484,1086,12301,1050078579 }, {46763,3991,4079,46512064}	30	30	Correct
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	27	Correct
67.	421, 1598, {53573,21470,17803,432455644} , {34772,50649,63478,727687663}	13	13	Correct
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	4	Correct
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