# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
114764 | 2019-06-02T15:17:51 Z | faustaadp | Simurgh (IOI17_simurgh) | C++17 | 141 ms | 3588 KB |
#include "simurgh.h" #include<bits/stdc++.h> typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; ll n,m,p[550],i,tim; ll X[125050]; ll Y[125050]; ll b[125050]; vector<int> r; vector<pair<ll,ll> > isi; ll car(ll aa) { if(p[aa]==aa) return aa; else return p[aa]=car(p[aa]); } void cek(ll aa) { vector<int> tan; ll ii; for(ii=0;ii<n;ii++)p[ii]=ii; for(ii=0;ii<r.size();ii++) if(ii!=aa) { p[car(X[r[ii]])]=car(Y[r[ii]]); tan.pb(r[ii]); } ll mi=tim,ya=0,ma=-1; for(ii=0;ii<m;ii++) if(car(X[ii])!=car(Y[ii])) { if(b[ii]==1) { r[aa]=ii; return ; } } for(ii=0;ii<m;ii++) if(car(X[ii])!=car(Y[ii])) { // cout<<aa<<" "<<ii<<"\n"; //b[ii]=1; if(b[ii]==2) continue; tan.pb(ii); ll tom=count_common_roads(tan); mi=min(mi,tom); tan.pop_back(); isi.pb(mp(-tom,ii)); /* if(tom>mi) { // ya=1; break; }*/ } // cout<<aa<<" "<<ya<<"\n"; //if(!ya) // return ; if(isi.empty()) return ; sort(isi.begin(),isi.end()); for(ii=0;ii<isi.size();ii++) if(isi[0].fi==isi[ii].fi) b[isi[ii].se]=1; else b[isi[ii].se]=2; r[aa]=isi[0].se; tim=-isi[0].fi; } std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) { n=N; m=U.size(); for(i=0;i<m;i++) X[i]=U[i]; for(i=0;i<m;i++) Y[i]=V[i]; for(i=0;i<n;i++)p[i]=i; for(i=0;i<m;i++) if(car(U[i])!=car(V[i])) { p[car(U[i])]=car(V[i]); r.pb(i); } //while(1); tim=count_common_roads(r); for(i=0;i<r.size();i++) { isi.clear(); cek(i); // cout<<i<<" "<<r[i]<<"\n"; } //for(i=0;i<r.size();i++) return r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | correct |
2 | Correct | 2 ms | 384 KB | correct |
3 | Correct | 2 ms | 384 KB | correct |
4 | Correct | 2 ms | 384 KB | correct |
5 | Correct | 2 ms | 384 KB | correct |
6 | Correct | 2 ms | 384 KB | correct |
7 | Correct | 2 ms | 384 KB | correct |
8 | Correct | 2 ms | 384 KB | correct |
9 | Correct | 2 ms | 384 KB | correct |
10 | Correct | 2 ms | 384 KB | correct |
11 | Correct | 2 ms | 384 KB | correct |
12 | Correct | 2 ms | 384 KB | correct |
13 | Correct | 2 ms | 384 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | correct |
2 | Correct | 2 ms | 384 KB | correct |
3 | Correct | 2 ms | 384 KB | correct |
4 | Correct | 2 ms | 384 KB | correct |
5 | Correct | 2 ms | 384 KB | correct |
6 | Correct | 2 ms | 384 KB | correct |
7 | Correct | 2 ms | 384 KB | correct |
8 | Correct | 2 ms | 384 KB | correct |
9 | Correct | 2 ms | 384 KB | correct |
10 | Correct | 2 ms | 384 KB | correct |
11 | Correct | 2 ms | 384 KB | correct |
12 | Correct | 2 ms | 384 KB | correct |
13 | Correct | 2 ms | 384 KB | correct |
14 | Correct | 3 ms | 384 KB | correct |
15 | Correct | 3 ms | 384 KB | correct |
16 | Correct | 3 ms | 384 KB | correct |
17 | Correct | 3 ms | 384 KB | correct |
18 | Correct | 3 ms | 384 KB | correct |
19 | Correct | 3 ms | 384 KB | correct |
20 | Correct | 3 ms | 384 KB | correct |
21 | Correct | 4 ms | 384 KB | correct |
22 | Correct | 4 ms | 384 KB | correct |
23 | Correct | 3 ms | 384 KB | correct |
24 | Correct | 3 ms | 384 KB | correct |
25 | Correct | 3 ms | 384 KB | correct |
26 | Correct | 3 ms | 384 KB | correct |
27 | Correct | 3 ms | 384 KB | correct |
28 | Correct | 3 ms | 384 KB | correct |
29 | Correct | 2 ms | 384 KB | correct |
30 | Correct | 3 ms | 384 KB | correct |
31 | Correct | 3 ms | 384 KB | correct |
32 | Correct | 3 ms | 384 KB | correct |
33 | Correct | 3 ms | 384 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | correct |
2 | Correct | 2 ms | 384 KB | correct |
3 | Correct | 2 ms | 384 KB | correct |
4 | Correct | 2 ms | 384 KB | correct |
5 | Correct | 2 ms | 384 KB | correct |
6 | Correct | 2 ms | 384 KB | correct |
7 | Correct | 2 ms | 384 KB | correct |
8 | Correct | 2 ms | 384 KB | correct |
9 | Correct | 2 ms | 384 KB | correct |
10 | Correct | 2 ms | 384 KB | correct |
11 | Correct | 2 ms | 384 KB | correct |
12 | Correct | 2 ms | 384 KB | correct |
13 | Correct | 2 ms | 384 KB | correct |
14 | Correct | 3 ms | 384 KB | correct |
15 | Correct | 3 ms | 384 KB | correct |
16 | Correct | 3 ms | 384 KB | correct |
17 | Correct | 3 ms | 384 KB | correct |
18 | Correct | 3 ms | 384 KB | correct |
19 | Correct | 3 ms | 384 KB | correct |
20 | Correct | 3 ms | 384 KB | correct |
21 | Correct | 4 ms | 384 KB | correct |
22 | Correct | 4 ms | 384 KB | correct |
23 | Correct | 3 ms | 384 KB | correct |
24 | Correct | 3 ms | 384 KB | correct |
25 | Correct | 3 ms | 384 KB | correct |
26 | Correct | 3 ms | 384 KB | correct |
27 | Correct | 3 ms | 384 KB | correct |
28 | Correct | 3 ms | 384 KB | correct |
29 | Correct | 2 ms | 384 KB | correct |
30 | Correct | 3 ms | 384 KB | correct |
31 | Correct | 3 ms | 384 KB | correct |
32 | Correct | 3 ms | 384 KB | correct |
33 | Correct | 3 ms | 384 KB | correct |
34 | Correct | 139 ms | 1696 KB | correct |
35 | Correct | 141 ms | 2144 KB | correct |
36 | Correct | 96 ms | 1384 KB | correct |
37 | Correct | 11 ms | 380 KB | correct |
38 | Correct | 133 ms | 1884 KB | correct |
39 | Correct | 135 ms | 1784 KB | correct |
40 | Correct | 95 ms | 1408 KB | correct |
41 | Correct | 69 ms | 2072 KB | correct |
42 | Correct | 123 ms | 2012 KB | correct |
43 | Correct | 93 ms | 1280 KB | correct |
44 | Correct | 74 ms | 1024 KB | correct |
45 | Correct | 88 ms | 1152 KB | correct |
46 | Correct | 65 ms | 896 KB | correct |
47 | Correct | 31 ms | 760 KB | correct |
48 | Correct | 6 ms | 384 KB | correct |
49 | Correct | 11 ms | 384 KB | correct |
50 | Correct | 30 ms | 640 KB | correct |
51 | Correct | 88 ms | 1152 KB | correct |
52 | Correct | 78 ms | 1024 KB | correct |
53 | Correct | 67 ms | 896 KB | correct |
54 | Correct | 92 ms | 1152 KB | correct |
55 | Correct | 91 ms | 1272 KB | correct |
56 | Correct | 86 ms | 1196 KB | correct |
57 | Correct | 85 ms | 1244 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | correct |
2 | Correct | 2 ms | 384 KB | correct |
3 | Incorrect | 98 ms | 3588 KB | WA in grader: NO |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | correct |
2 | Correct | 2 ms | 384 KB | correct |
3 | Correct | 2 ms | 384 KB | correct |
4 | Correct | 2 ms | 384 KB | correct |
5 | Correct | 2 ms | 384 KB | correct |
6 | Correct | 2 ms | 384 KB | correct |
7 | Correct | 2 ms | 384 KB | correct |
8 | Correct | 2 ms | 384 KB | correct |
9 | Correct | 2 ms | 384 KB | correct |
10 | Correct | 2 ms | 384 KB | correct |
11 | Correct | 2 ms | 384 KB | correct |
12 | Correct | 2 ms | 384 KB | correct |
13 | Correct | 2 ms | 384 KB | correct |
14 | Correct | 3 ms | 384 KB | correct |
15 | Correct | 3 ms | 384 KB | correct |
16 | Correct | 3 ms | 384 KB | correct |
17 | Correct | 3 ms | 384 KB | correct |
18 | Correct | 3 ms | 384 KB | correct |
19 | Correct | 3 ms | 384 KB | correct |
20 | Correct | 3 ms | 384 KB | correct |
21 | Correct | 4 ms | 384 KB | correct |
22 | Correct | 4 ms | 384 KB | correct |
23 | Correct | 3 ms | 384 KB | correct |
24 | Correct | 3 ms | 384 KB | correct |
25 | Correct | 3 ms | 384 KB | correct |
26 | Correct | 3 ms | 384 KB | correct |
27 | Correct | 3 ms | 384 KB | correct |
28 | Correct | 3 ms | 384 KB | correct |
29 | Correct | 2 ms | 384 KB | correct |
30 | Correct | 3 ms | 384 KB | correct |
31 | Correct | 3 ms | 384 KB | correct |
32 | Correct | 3 ms | 384 KB | correct |
33 | Correct | 3 ms | 384 KB | correct |
34 | Correct | 139 ms | 1696 KB | correct |
35 | Correct | 141 ms | 2144 KB | correct |
36 | Correct | 96 ms | 1384 KB | correct |
37 | Correct | 11 ms | 380 KB | correct |
38 | Correct | 133 ms | 1884 KB | correct |
39 | Correct | 135 ms | 1784 KB | correct |
40 | Correct | 95 ms | 1408 KB | correct |
41 | Correct | 69 ms | 2072 KB | correct |
42 | Correct | 123 ms | 2012 KB | correct |
43 | Correct | 93 ms | 1280 KB | correct |
44 | Correct | 74 ms | 1024 KB | correct |
45 | Correct | 88 ms | 1152 KB | correct |
46 | Correct | 65 ms | 896 KB | correct |
47 | Correct | 31 ms | 760 KB | correct |
48 | Correct | 6 ms | 384 KB | correct |
49 | Correct | 11 ms | 384 KB | correct |
50 | Correct | 30 ms | 640 KB | correct |
51 | Correct | 88 ms | 1152 KB | correct |
52 | Correct | 78 ms | 1024 KB | correct |
53 | Correct | 67 ms | 896 KB | correct |
54 | Correct | 92 ms | 1152 KB | correct |
55 | Correct | 91 ms | 1272 KB | correct |
56 | Correct | 86 ms | 1196 KB | correct |
57 | Correct | 85 ms | 1244 KB | correct |
58 | Correct | 2 ms | 384 KB | correct |
59 | Correct | 2 ms | 384 KB | correct |
60 | Incorrect | 98 ms | 3588 KB | WA in grader: NO |
61 | Halted | 0 ms | 0 KB | - |