# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
726856 | 2023-04-19T12:51:08 Z | alvingogo | Split the Attractions (IOI19_split) | C++14 | 177 ms | 27152 KB |
#include "split.h" #include <bits/stdc++.h> //#include "grader.cpp" #define fs first #define sc second using namespace std; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m=p.size(); vector<vector<int> > e(n); for(int i=0;i<m;i++){ e[p[i]].push_back(q[i]); e[q[i]].push_back(p[i]); } vector<int> ans(n); pair<int,int> rk[3]={{a,1},{b,2},{c,3}}; if(a>b){ swap(rk[0],rk[1]); } if(b>c){ swap(rk[1],rk[2]); } vector<int> vis(n),vis2(n); int flag=0; vector<int> sz(n),dep(n); function<void(int)> dfs3=[&](int r){ ans[r]=rk[1].sc; vis2[r]=1; rk[1].fs--; if(rk[1].fs==0){ return; } for(auto h:e[r]){ if(!vis2[h]){ dfs3(h); if(rk[1].fs==0){ return; } } } }; function<void(int)> dfs2=[&](int r){ ans[r]=rk[0].sc; vis2[r]=1; rk[0].fs--; if(rk[0].fs==0){ return; } for(auto h:e[r]){ if(dep[h]==dep[r]+1){ dfs2(h); if(rk[0].fs==0){ return; } } } }; function<int(int,int)> dfs=[&](int r,int d){ dep[r]=d; vis[r]=1; sz[r]=1; int f3=0; int x=1e9; vector<pair<int,int> > zz; for(auto h:e[r]){ if(!vis[h]){ int u=dfs(h,d+1); x=min(x,u); if(u<dep[r]){ zz.push_back({sz[h],h}); } sz[r]+=sz[h]; if(sz[h]>=rk[0].fs){ f3=1; } if(flag){ return (int)1e9; } } else{ x=min(x,dep[h]); } } if(flag){ return (int)1e9; } if(!f3){ if(sz[r]>=rk[0].fs){ int u=n-sz[r]; int f2=0; for(int i=0;i<=zz.size();i++){ if(u>=rk[1].fs){ dfs2(r); for(auto h:e[r]){ if(dep[h]==dep[r]-1){ dfs3(h); break; } } break; } if(i==zz.size()){ f2=1; break; } u+=zz[i].fs; dep[zz[i].sc]=-2; } if(f2){ } else{ for(int j=0;j<n;j++){ if(ans[j]==0){ ans[j]=rk[2].sc; } } flag=1; return (int)1e9; } } } return x; }; dfs(0,0); if(flag){ return ans; } swap(rk[0],rk[1]); fill(vis.begin(),vis.end(),0); fill(sz.begin(),sz.end(),0); fill(dep.begin(),dep.end(),0); dfs(0,0); return ans;}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 KB | ok, correct split |
2 | Correct | 1 ms | 300 KB | ok, correct split |
3 | Correct | 1 ms | 304 KB | ok, correct split |
4 | Correct | 1 ms | 212 KB | ok, correct split |
5 | Correct | 1 ms | 304 KB | ok, correct split |
6 | Correct | 1 ms | 300 KB | ok, correct split |
7 | Correct | 107 ms | 26308 KB | ok, correct split |
8 | Correct | 80 ms | 15592 KB | ok, correct split |
9 | Correct | 84 ms | 19796 KB | ok, correct split |
10 | Correct | 123 ms | 27096 KB | ok, correct split |
11 | Correct | 101 ms | 27152 KB | ok, correct split |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | ok, correct split |
2 | Correct | 1 ms | 300 KB | ok, correct split |
3 | Correct | 1 ms | 296 KB | ok, correct split |
4 | Correct | 98 ms | 11240 KB | ok, correct split |
5 | Correct | 70 ms | 10000 KB | ok, correct split |
6 | Correct | 83 ms | 27112 KB | ok, correct split |
7 | Correct | 92 ms | 23936 KB | ok, correct split |
8 | Correct | 104 ms | 12728 KB | ok, correct split |
9 | Correct | 68 ms | 10232 KB | ok, correct split |
10 | Correct | 50 ms | 10288 KB | ok, correct split |
11 | Correct | 53 ms | 10232 KB | ok, correct split |
12 | Correct | 67 ms | 10240 KB | ok, correct split |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 232 KB | ok, correct split |
2 | Correct | 112 ms | 10068 KB | ok, correct split |
3 | Correct | 22 ms | 4368 KB | ok, correct split |
4 | Correct | 1 ms | 212 KB | ok, correct split |
5 | Correct | 81 ms | 15596 KB | ok, correct split |
6 | Correct | 97 ms | 15124 KB | ok, correct split |
7 | Correct | 101 ms | 14736 KB | ok, correct split |
8 | Correct | 79 ms | 17716 KB | ok, correct split |
9 | Correct | 130 ms | 14292 KB | ok, correct split |
10 | Correct | 21 ms | 3668 KB | ok, no valid answer |
11 | Correct | 39 ms | 5392 KB | ok, no valid answer |
12 | Correct | 80 ms | 10228 KB | ok, no valid answer |
13 | Correct | 78 ms | 10016 KB | ok, no valid answer |
14 | Correct | 67 ms | 10384 KB | ok, no valid answer |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | ok, correct split |
2 | Correct | 1 ms | 212 KB | ok, no valid answer |
3 | Correct | 1 ms | 300 KB | ok, correct split |
4 | Correct | 1 ms | 212 KB | ok, correct split |
5 | Correct | 1 ms | 212 KB | ok, correct split |
6 | Correct | 1 ms | 296 KB | ok, correct split |
7 | Correct | 1 ms | 308 KB | ok, correct split |
8 | Correct | 1 ms | 212 KB | ok, correct split |
9 | Correct | 2 ms | 724 KB | ok, correct split |
10 | Correct | 3 ms | 568 KB | ok, correct split |
11 | Correct | 1 ms | 340 KB | ok, correct split |
12 | Correct | 3 ms | 564 KB | ok, correct split |
13 | Correct | 1 ms | 212 KB | ok, correct split |
14 | Correct | 1 ms | 212 KB | ok, correct split |
15 | Correct | 1 ms | 212 KB | ok, correct split |
16 | Correct | 1 ms | 212 KB | ok, correct split |
17 | Correct | 1 ms | 300 KB | ok, correct split |
18 | Correct | 1 ms | 296 KB | ok, correct split |
19 | Correct | 1 ms | 340 KB | ok, correct split |
20 | Correct | 1 ms | 468 KB | ok, correct split |
21 | Correct | 2 ms | 596 KB | ok, correct split |
22 | Correct | 3 ms | 596 KB | ok, correct split |
23 | Correct | 4 ms | 724 KB | ok, correct split |
24 | Correct | 2 ms | 596 KB | ok, correct split |
25 | Correct | 2 ms | 596 KB | ok, correct split |
26 | Correct | 4 ms | 568 KB | ok, correct split |
27 | Correct | 3 ms | 684 KB | ok, correct split |
28 | Correct | 2 ms | 596 KB | ok, correct split |
29 | Correct | 1 ms | 340 KB | ok, correct split |
30 | Correct | 2 ms | 572 KB | ok, correct split |
31 | Correct | 1 ms | 340 KB | ok, correct split |
32 | Correct | 1 ms | 212 KB | ok, correct split |
33 | Correct | 1 ms | 304 KB | ok, correct split |
34 | Correct | 2 ms | 572 KB | ok, correct split |
35 | Correct | 2 ms | 468 KB | ok, correct split |
36 | Correct | 2 ms | 440 KB | ok, correct split |
37 | Correct | 3 ms | 596 KB | ok, correct split |
38 | Correct | 3 ms | 652 KB | ok, correct split |
39 | Correct | 3 ms | 572 KB | ok, correct split |
40 | Correct | 3 ms | 644 KB | ok, correct split |
41 | Correct | 2 ms | 480 KB | ok, correct split |
42 | Correct | 2 ms | 480 KB | ok, correct split |
43 | Correct | 5 ms | 596 KB | ok, correct split |
44 | Correct | 3 ms | 596 KB | ok, correct split |
45 | Correct | 3 ms | 600 KB | ok, correct split |
46 | Correct | 2 ms | 720 KB | ok, correct split |
47 | Correct | 2 ms | 692 KB | ok, no valid answer |
48 | Correct | 2 ms | 472 KB | ok, correct split |
49 | Correct | 2 ms | 708 KB | ok, correct split |
50 | Correct | 1 ms | 212 KB | ok, no valid answer |
51 | Correct | 1 ms | 212 KB | ok, no valid answer |
52 | Correct | 2 ms | 468 KB | ok, no valid answer |
53 | Correct | 5 ms | 608 KB | ok, no valid answer |
54 | Correct | 2 ms | 480 KB | ok, no valid answer |
55 | Correct | 2 ms | 468 KB | ok, no valid answer |
56 | Correct | 2 ms | 568 KB | ok, no valid answer |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 KB | ok, correct split |
2 | Correct | 1 ms | 300 KB | ok, correct split |
3 | Correct | 1 ms | 304 KB | ok, correct split |
4 | Correct | 1 ms | 212 KB | ok, correct split |
5 | Correct | 1 ms | 304 KB | ok, correct split |
6 | Correct | 1 ms | 300 KB | ok, correct split |
7 | Correct | 107 ms | 26308 KB | ok, correct split |
8 | Correct | 80 ms | 15592 KB | ok, correct split |
9 | Correct | 84 ms | 19796 KB | ok, correct split |
10 | Correct | 123 ms | 27096 KB | ok, correct split |
11 | Correct | 101 ms | 27152 KB | ok, correct split |
12 | Correct | 1 ms | 212 KB | ok, correct split |
13 | Correct | 1 ms | 300 KB | ok, correct split |
14 | Correct | 1 ms | 296 KB | ok, correct split |
15 | Correct | 98 ms | 11240 KB | ok, correct split |
16 | Correct | 70 ms | 10000 KB | ok, correct split |
17 | Correct | 83 ms | 27112 KB | ok, correct split |
18 | Correct | 92 ms | 23936 KB | ok, correct split |
19 | Correct | 104 ms | 12728 KB | ok, correct split |
20 | Correct | 68 ms | 10232 KB | ok, correct split |
21 | Correct | 50 ms | 10288 KB | ok, correct split |
22 | Correct | 53 ms | 10232 KB | ok, correct split |
23 | Correct | 67 ms | 10240 KB | ok, correct split |
24 | Correct | 1 ms | 232 KB | ok, correct split |
25 | Correct | 112 ms | 10068 KB | ok, correct split |
26 | Correct | 22 ms | 4368 KB | ok, correct split |
27 | Correct | 1 ms | 212 KB | ok, correct split |
28 | Correct | 81 ms | 15596 KB | ok, correct split |
29 | Correct | 97 ms | 15124 KB | ok, correct split |
30 | Correct | 101 ms | 14736 KB | ok, correct split |
31 | Correct | 79 ms | 17716 KB | ok, correct split |
32 | Correct | 130 ms | 14292 KB | ok, correct split |
33 | Correct | 21 ms | 3668 KB | ok, no valid answer |
34 | Correct | 39 ms | 5392 KB | ok, no valid answer |
35 | Correct | 80 ms | 10228 KB | ok, no valid answer |
36 | Correct | 78 ms | 10016 KB | ok, no valid answer |
37 | Correct | 67 ms | 10384 KB | ok, no valid answer |
38 | Correct | 1 ms | 212 KB | ok, correct split |
39 | Correct | 1 ms | 212 KB | ok, no valid answer |
40 | Correct | 1 ms | 300 KB | ok, correct split |
41 | Correct | 1 ms | 212 KB | ok, correct split |
42 | Correct | 1 ms | 212 KB | ok, correct split |
43 | Correct | 1 ms | 296 KB | ok, correct split |
44 | Correct | 1 ms | 308 KB | ok, correct split |
45 | Correct | 1 ms | 212 KB | ok, correct split |
46 | Correct | 2 ms | 724 KB | ok, correct split |
47 | Correct | 3 ms | 568 KB | ok, correct split |
48 | Correct | 1 ms | 340 KB | ok, correct split |
49 | Correct | 3 ms | 564 KB | ok, correct split |
50 | Correct | 1 ms | 212 KB | ok, correct split |
51 | Correct | 1 ms | 212 KB | ok, correct split |
52 | Correct | 1 ms | 212 KB | ok, correct split |
53 | Correct | 1 ms | 212 KB | ok, correct split |
54 | Correct | 1 ms | 300 KB | ok, correct split |
55 | Correct | 1 ms | 296 KB | ok, correct split |
56 | Correct | 1 ms | 340 KB | ok, correct split |
57 | Correct | 1 ms | 468 KB | ok, correct split |
58 | Correct | 2 ms | 596 KB | ok, correct split |
59 | Correct | 3 ms | 596 KB | ok, correct split |
60 | Correct | 4 ms | 724 KB | ok, correct split |
61 | Correct | 2 ms | 596 KB | ok, correct split |
62 | Correct | 2 ms | 596 KB | ok, correct split |
63 | Correct | 4 ms | 568 KB | ok, correct split |
64 | Correct | 3 ms | 684 KB | ok, correct split |
65 | Correct | 2 ms | 596 KB | ok, correct split |
66 | Correct | 1 ms | 340 KB | ok, correct split |
67 | Correct | 2 ms | 572 KB | ok, correct split |
68 | Correct | 1 ms | 340 KB | ok, correct split |
69 | Correct | 1 ms | 212 KB | ok, correct split |
70 | Correct | 1 ms | 304 KB | ok, correct split |
71 | Correct | 2 ms | 572 KB | ok, correct split |
72 | Correct | 2 ms | 468 KB | ok, correct split |
73 | Correct | 2 ms | 440 KB | ok, correct split |
74 | Correct | 3 ms | 596 KB | ok, correct split |
75 | Correct | 3 ms | 652 KB | ok, correct split |
76 | Correct | 3 ms | 572 KB | ok, correct split |
77 | Correct | 3 ms | 644 KB | ok, correct split |
78 | Correct | 2 ms | 480 KB | ok, correct split |
79 | Correct | 2 ms | 480 KB | ok, correct split |
80 | Correct | 5 ms | 596 KB | ok, correct split |
81 | Correct | 3 ms | 596 KB | ok, correct split |
82 | Correct | 3 ms | 600 KB | ok, correct split |
83 | Correct | 2 ms | 720 KB | ok, correct split |
84 | Correct | 2 ms | 692 KB | ok, no valid answer |
85 | Correct | 2 ms | 472 KB | ok, correct split |
86 | Correct | 2 ms | 708 KB | ok, correct split |
87 | Correct | 1 ms | 212 KB | ok, no valid answer |
88 | Correct | 1 ms | 212 KB | ok, no valid answer |
89 | Correct | 2 ms | 468 KB | ok, no valid answer |
90 | Correct | 5 ms | 608 KB | ok, no valid answer |
91 | Correct | 2 ms | 480 KB | ok, no valid answer |
92 | Correct | 2 ms | 468 KB | ok, no valid answer |
93 | Correct | 2 ms | 568 KB | ok, no valid answer |
94 | Correct | 88 ms | 17268 KB | ok, correct split |
95 | Correct | 177 ms | 24764 KB | ok, correct split |
96 | Correct | 145 ms | 22468 KB | ok, correct split |
97 | Correct | 23 ms | 4420 KB | ok, correct split |
98 | Correct | 23 ms | 4568 KB | ok, correct split |
99 | Correct | 52 ms | 7984 KB | ok, correct split |
100 | Correct | 126 ms | 14772 KB | ok, correct split |
101 | Correct | 85 ms | 13532 KB | ok, correct split |
102 | Correct | 99 ms | 12628 KB | ok, correct split |
103 | Correct | 91 ms | 12432 KB | ok, correct split |
104 | Correct | 108 ms | 14748 KB | ok, correct split |
105 | Correct | 44 ms | 6788 KB | ok, correct split |
106 | Correct | 109 ms | 14992 KB | ok, correct split |
107 | Correct | 69 ms | 10512 KB | ok, correct split |
108 | Correct | 85 ms | 10528 KB | ok, correct split |
109 | Correct | 143 ms | 13864 KB | ok, correct split |
110 | Correct | 145 ms | 13612 KB | ok, correct split |
111 | Correct | 136 ms | 13716 KB | ok, correct split |
112 | Correct | 135 ms | 13884 KB | ok, correct split |
113 | Correct | 122 ms | 13896 KB | ok, correct split |
114 | Correct | 12 ms | 2348 KB | ok, correct split |
115 | Correct | 11 ms | 1888 KB | ok, correct split |
116 | Correct | 139 ms | 13608 KB | ok, correct split |
117 | Correct | 156 ms | 13448 KB | ok, correct split |
118 | Correct | 91 ms | 10652 KB | ok, correct split |
119 | Correct | 60 ms | 10536 KB | ok, correct split |
120 | Correct | 84 ms | 19628 KB | ok, correct split |
121 | Correct | 103 ms | 10444 KB | ok, no valid answer |
122 | Correct | 85 ms | 10612 KB | ok, no valid answer |
123 | Correct | 151 ms | 15296 KB | ok, no valid answer |
124 | Correct | 137 ms | 14900 KB | ok, no valid answer |
125 | Correct | 105 ms | 11588 KB | ok, no valid answer |
126 | Correct | 46 ms | 9804 KB | ok, no valid answer |
127 | Correct | 82 ms | 12100 KB | ok, no valid answer |