# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289496 | 2020-09-02T17:09:48 Z | eohomegrownapps | Simurgh (IOI17_simurgh) | C++14 | 204 ms | 3204 KB |
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; //count_common_roads vector<int> u; vector<int> v; vector<int> royal; // -1 int n; int e; //int count_common_roads(vector<int> &r) struct UFDS{ int n; vector<int> parent; UFDS(int _n){ n = _n; parent.resize(n); for (int i = 0; i<n; i++){ parent[i]=i; } } int root(int i){ if (parent[i]==i){return i;} return parent[i]=root(parent[i]); } void connect(int a, int b){ int ra = root(a); int rb = root(b); if (ra==rb){return;} parent[ra]=rb; } bool connected(int a, int b){ return root(a) == root(b); } }; std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) { n=N; u=U; v=V; e=u.size(); royal.resize(e,-1); vector<int> ans; while (ans.size()<n-1){ /*cout<<"royal: "; for (int i : ans){ cout<<i<<' '; }cout<<endl;*/ UFDS ufds(n); // add all royal roads first vector<int> mst; for (int i = 0; i<e; i++){ if (royal[i]==1){ mst.push_back(i); ufds.connect(u[i],v[i]); } } for (int i = 0; i<e; i++){ if (mst.size()==n-2){ break; } if (royal[i]==-1 && !ufds.connected(u[i],v[i])){ mst.push_back(i); ufds.connect(u[i],v[i]); } } /*for (int i : mst){ cout<<i<<' '; }cout<<endl;*/ // try all edges vector<int> edges; vector<int> values; int maxval = 0; for (int i = 0; i<e; i++){ if (royal[i]!=-1){continue;} if (ufds.connected(u[i],v[i])){continue;} // try connecting edge mst.push_back(i); values.push_back(count_common_roads(mst)); mst.pop_back(); edges.push_back(i); maxval=max(maxval,values.back()); } for (int i = 0; i<edges.size(); i++){ if (values[i]==maxval){ royal[edges[i]]=1; ans.push_back(edges[i]); } else { royal[edges[i]]=0; } } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | correct |
2 | Correct | 0 ms | 256 KB | correct |
3 | Correct | 1 ms | 256 KB | correct |
4 | Correct | 0 ms | 256 KB | correct |
5 | Correct | 1 ms | 256 KB | correct |
6 | Correct | 0 ms | 256 KB | correct |
7 | Correct | 0 ms | 256 KB | correct |
8 | Correct | 1 ms | 256 KB | correct |
9 | Correct | 0 ms | 256 KB | correct |
10 | Correct | 1 ms | 256 KB | correct |
11 | Correct | 0 ms | 256 KB | correct |
12 | Correct | 0 ms | 256 KB | correct |
13 | Correct | 0 ms | 256 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | correct |
2 | Correct | 0 ms | 256 KB | correct |
3 | Correct | 1 ms | 256 KB | correct |
4 | Correct | 0 ms | 256 KB | correct |
5 | Correct | 1 ms | 256 KB | correct |
6 | Correct | 0 ms | 256 KB | correct |
7 | Correct | 0 ms | 256 KB | correct |
8 | Correct | 1 ms | 256 KB | correct |
9 | Correct | 0 ms | 256 KB | correct |
10 | Correct | 1 ms | 256 KB | correct |
11 | Correct | 0 ms | 256 KB | correct |
12 | Correct | 0 ms | 256 KB | correct |
13 | Correct | 0 ms | 256 KB | correct |
14 | Correct | 3 ms | 416 KB | correct |
15 | Correct | 2 ms | 384 KB | correct |
16 | Correct | 2 ms | 384 KB | correct |
17 | Correct | 2 ms | 384 KB | correct |
18 | Correct | 2 ms | 384 KB | correct |
19 | Correct | 2 ms | 384 KB | correct |
20 | Correct | 2 ms | 384 KB | correct |
21 | Correct | 2 ms | 384 KB | correct |
22 | Correct | 2 ms | 384 KB | correct |
23 | Correct | 2 ms | 384 KB | correct |
24 | Correct | 2 ms | 384 KB | correct |
25 | Correct | 1 ms | 256 KB | correct |
26 | Correct | 2 ms | 384 KB | correct |
27 | Correct | 2 ms | 384 KB | correct |
28 | Correct | 1 ms | 384 KB | correct |
29 | Correct | 1 ms | 256 KB | correct |
30 | Correct | 2 ms | 384 KB | correct |
31 | Correct | 2 ms | 384 KB | correct |
32 | Correct | 2 ms | 396 KB | correct |
33 | Correct | 2 ms | 384 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | correct |
2 | Correct | 0 ms | 256 KB | correct |
3 | Correct | 1 ms | 256 KB | correct |
4 | Correct | 0 ms | 256 KB | correct |
5 | Correct | 1 ms | 256 KB | correct |
6 | Correct | 0 ms | 256 KB | correct |
7 | Correct | 0 ms | 256 KB | correct |
8 | Correct | 1 ms | 256 KB | correct |
9 | Correct | 0 ms | 256 KB | correct |
10 | Correct | 1 ms | 256 KB | correct |
11 | Correct | 0 ms | 256 KB | correct |
12 | Correct | 0 ms | 256 KB | correct |
13 | Correct | 0 ms | 256 KB | correct |
14 | Correct | 3 ms | 416 KB | correct |
15 | Correct | 2 ms | 384 KB | correct |
16 | Correct | 2 ms | 384 KB | correct |
17 | Correct | 2 ms | 384 KB | correct |
18 | Correct | 2 ms | 384 KB | correct |
19 | Correct | 2 ms | 384 KB | correct |
20 | Correct | 2 ms | 384 KB | correct |
21 | Correct | 2 ms | 384 KB | correct |
22 | Correct | 2 ms | 384 KB | correct |
23 | Correct | 2 ms | 384 KB | correct |
24 | Correct | 2 ms | 384 KB | correct |
25 | Correct | 1 ms | 256 KB | correct |
26 | Correct | 2 ms | 384 KB | correct |
27 | Correct | 2 ms | 384 KB | correct |
28 | Correct | 1 ms | 384 KB | correct |
29 | Correct | 1 ms | 256 KB | correct |
30 | Correct | 2 ms | 384 KB | correct |
31 | Correct | 2 ms | 384 KB | correct |
32 | Correct | 2 ms | 396 KB | correct |
33 | Correct | 2 ms | 384 KB | correct |
34 | Correct | 204 ms | 1400 KB | correct |
35 | Correct | 192 ms | 1400 KB | correct |
36 | Correct | 135 ms | 1152 KB | correct |
37 | Correct | 10 ms | 384 KB | correct |
38 | Correct | 192 ms | 1360 KB | correct |
39 | Correct | 177 ms | 1272 KB | correct |
40 | Correct | 140 ms | 1024 KB | correct |
41 | Correct | 96 ms | 1280 KB | correct |
42 | Correct | 171 ms | 1280 KB | correct |
43 | Correct | 111 ms | 888 KB | correct |
44 | Correct | 96 ms | 768 KB | correct |
45 | Correct | 113 ms | 896 KB | correct |
46 | Correct | 84 ms | 760 KB | correct |
47 | Correct | 37 ms | 512 KB | correct |
48 | Correct | 6 ms | 384 KB | correct |
49 | Correct | 13 ms | 384 KB | correct |
50 | Correct | 37 ms | 512 KB | correct |
51 | Correct | 108 ms | 888 KB | correct |
52 | Correct | 92 ms | 768 KB | correct |
53 | Correct | 83 ms | 768 KB | correct |
54 | Correct | 112 ms | 896 KB | correct |
55 | Correct | 97 ms | 888 KB | correct |
56 | Correct | 97 ms | 888 KB | correct |
57 | Correct | 96 ms | 888 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | correct |
2 | Correct | 0 ms | 256 KB | correct |
3 | Incorrect | 171 ms | 3204 KB | WA in grader: NO |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | correct |
2 | Correct | 0 ms | 256 KB | correct |
3 | Correct | 1 ms | 256 KB | correct |
4 | Correct | 0 ms | 256 KB | correct |
5 | Correct | 1 ms | 256 KB | correct |
6 | Correct | 0 ms | 256 KB | correct |
7 | Correct | 0 ms | 256 KB | correct |
8 | Correct | 1 ms | 256 KB | correct |
9 | Correct | 0 ms | 256 KB | correct |
10 | Correct | 1 ms | 256 KB | correct |
11 | Correct | 0 ms | 256 KB | correct |
12 | Correct | 0 ms | 256 KB | correct |
13 | Correct | 0 ms | 256 KB | correct |
14 | Correct | 3 ms | 416 KB | correct |
15 | Correct | 2 ms | 384 KB | correct |
16 | Correct | 2 ms | 384 KB | correct |
17 | Correct | 2 ms | 384 KB | correct |
18 | Correct | 2 ms | 384 KB | correct |
19 | Correct | 2 ms | 384 KB | correct |
20 | Correct | 2 ms | 384 KB | correct |
21 | Correct | 2 ms | 384 KB | correct |
22 | Correct | 2 ms | 384 KB | correct |
23 | Correct | 2 ms | 384 KB | correct |
24 | Correct | 2 ms | 384 KB | correct |
25 | Correct | 1 ms | 256 KB | correct |
26 | Correct | 2 ms | 384 KB | correct |
27 | Correct | 2 ms | 384 KB | correct |
28 | Correct | 1 ms | 384 KB | correct |
29 | Correct | 1 ms | 256 KB | correct |
30 | Correct | 2 ms | 384 KB | correct |
31 | Correct | 2 ms | 384 KB | correct |
32 | Correct | 2 ms | 396 KB | correct |
33 | Correct | 2 ms | 384 KB | correct |
34 | Correct | 204 ms | 1400 KB | correct |
35 | Correct | 192 ms | 1400 KB | correct |
36 | Correct | 135 ms | 1152 KB | correct |
37 | Correct | 10 ms | 384 KB | correct |
38 | Correct | 192 ms | 1360 KB | correct |
39 | Correct | 177 ms | 1272 KB | correct |
40 | Correct | 140 ms | 1024 KB | correct |
41 | Correct | 96 ms | 1280 KB | correct |
42 | Correct | 171 ms | 1280 KB | correct |
43 | Correct | 111 ms | 888 KB | correct |
44 | Correct | 96 ms | 768 KB | correct |
45 | Correct | 113 ms | 896 KB | correct |
46 | Correct | 84 ms | 760 KB | correct |
47 | Correct | 37 ms | 512 KB | correct |
48 | Correct | 6 ms | 384 KB | correct |
49 | Correct | 13 ms | 384 KB | correct |
50 | Correct | 37 ms | 512 KB | correct |
51 | Correct | 108 ms | 888 KB | correct |
52 | Correct | 92 ms | 768 KB | correct |
53 | Correct | 83 ms | 768 KB | correct |
54 | Correct | 112 ms | 896 KB | correct |
55 | Correct | 97 ms | 888 KB | correct |
56 | Correct | 97 ms | 888 KB | correct |
57 | Correct | 96 ms | 888 KB | correct |
58 | Correct | 1 ms | 256 KB | correct |
59 | Correct | 0 ms | 256 KB | correct |
60 | Incorrect | 171 ms | 3204 KB | WA in grader: NO |
61 | Halted | 0 ms | 0 KB | - |