// model_solution/split-kostka-greedy-dfs-tree.cpp
#include "bits/stdc++.h"
#include "split.h"
using namespace std;
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
srand(10);
int m = (int)p.size();
vector <pair <int, int> > sizes = {{a,1}, {b,2}, {c,3}};
sort(sizes.begin(), sizes.end());
a = sizes[0].first; b = sizes[1].first; c = sizes[2].first;
vector <vector <int> > G(n);
for(int i=0; i<m; i++) {
G[p[i]].push_back(q[i]);
G[q[i]].push_back(p[i]);
}
vector <vector <int> > T(n);
vector <int> subtree(n), par(n);
function <int(int)> dfs0 = [&](int v) {
subtree[v] = 1;
for(auto w : G[v]) if(!subtree[w]) {
subtree[v] += dfs0(w);
par[w] = v;
T[v].push_back(w);
T[w].push_back(v);
}
return subtree[v];
};
dfs0(0);
for(int i=0; i<n; i++) {
vector <bool> vis(n);
vector <int> C;
function <void(int, int, int)> dfs = [&](int v, int limit, int forbidden) {
if((int)C.size() == limit) return;
if(forbidden == v) return;
C.push_back(v);
vis[v] = true;
for(auto w : T[v]) if(!vis[w]) dfs(w, limit, forbidden);
};
if(subtree[i] >= a and subtree[i] <= n-b) {
vector <int> ret(n, sizes[2].second);
dfs(i, a, par[i]);
for(auto cc : C) ret[cc] = sizes[0].second;
C.clear();
dfs(par[i], b, i);
for(auto cc : C) ret[cc] = sizes[1].second;
return ret;
} else if(subtree[i] >= b and subtree[i] <= n-a) {
vector <int> ret(n, sizes[2].second);
dfs(i, b, par[i]);
for(auto cc : C) ret[cc] = sizes[1].second;
C.clear();
dfs(par[i], a, i);
for(auto cc : C) ret[cc] = sizes[0].second;
return ret;
}
}
return vector<int>(n, 0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
256 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
126 ms |
20344 KB |
ok, correct split |
8 |
Correct |
118 ms |
18168 KB |
ok, correct split |
9 |
Correct |
130 ms |
19060 KB |
ok, correct split |
10 |
Correct |
121 ms |
20276 KB |
ok, correct split |
11 |
Correct |
126 ms |
20728 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
380 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
155 ms |
17932 KB |
ok, correct split |
5 |
Correct |
146 ms |
14756 KB |
ok, correct split |
6 |
Correct |
125 ms |
20216 KB |
ok, correct split |
7 |
Correct |
127 ms |
19064 KB |
ok, correct split |
8 |
Correct |
177 ms |
16572 KB |
ok, correct split |
9 |
Correct |
131 ms |
14584 KB |
ok, correct split |
10 |
Correct |
109 ms |
15356 KB |
ok, correct split |
11 |
Correct |
115 ms |
15300 KB |
ok, correct split |
12 |
Correct |
99 ms |
15216 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
138 ms |
14616 KB |
ok, correct split |
3 |
Correct |
42 ms |
5876 KB |
ok, correct split |
4 |
Correct |
2 ms |
380 KB |
ok, correct split |
5 |
Correct |
185 ms |
17356 KB |
ok, correct split |
6 |
Correct |
142 ms |
17272 KB |
ok, correct split |
7 |
Correct |
186 ms |
17188 KB |
ok, correct split |
8 |
Correct |
174 ms |
17400 KB |
ok, correct split |
9 |
Correct |
220 ms |
17140 KB |
ok, correct split |
10 |
Correct |
54 ms |
4984 KB |
ok, no valid answer |
11 |
Correct |
81 ms |
7288 KB |
ok, no valid answer |
12 |
Correct |
198 ms |
14648 KB |
ok, no valid answer |
13 |
Correct |
201 ms |
14392 KB |
ok, no valid answer |
14 |
Correct |
185 ms |
14868 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
256 KB |
ok, correct split |
4 |
Correct |
2 ms |
256 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
2 ms |
376 KB |
ok, correct split |
8 |
Correct |
2 ms |
376 KB |
ok, correct split |
9 |
Correct |
5 ms |
760 KB |
ok, correct split |
10 |
Correct |
5 ms |
764 KB |
ok, correct split |
11 |
Correct |
2 ms |
376 KB |
ok, correct split |
12 |
Correct |
5 ms |
760 KB |
ok, correct split |
13 |
Correct |
2 ms |
256 KB |
ok, correct split |
14 |
Correct |
2 ms |
256 KB |
ok, correct split |
15 |
Correct |
2 ms |
376 KB |
ok, correct split |
16 |
Correct |
2 ms |
376 KB |
ok, correct split |
17 |
Correct |
2 ms |
256 KB |
ok, correct split |
18 |
Correct |
2 ms |
256 KB |
ok, correct split |
19 |
Correct |
2 ms |
376 KB |
ok, correct split |
20 |
Correct |
4 ms |
548 KB |
ok, correct split |
21 |
Correct |
5 ms |
760 KB |
ok, correct split |
22 |
Correct |
4 ms |
764 KB |
ok, correct split |
23 |
Correct |
4 ms |
760 KB |
ok, correct split |
24 |
Correct |
4 ms |
760 KB |
ok, correct split |
25 |
Correct |
4 ms |
760 KB |
ok, correct split |
26 |
Incorrect |
5 ms |
760 KB |
jury found a solution, contestant did not |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
256 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
376 KB |
ok, correct split |
6 |
Correct |
2 ms |
376 KB |
ok, correct split |
7 |
Correct |
126 ms |
20344 KB |
ok, correct split |
8 |
Correct |
118 ms |
18168 KB |
ok, correct split |
9 |
Correct |
130 ms |
19060 KB |
ok, correct split |
10 |
Correct |
121 ms |
20276 KB |
ok, correct split |
11 |
Correct |
126 ms |
20728 KB |
ok, correct split |
12 |
Correct |
2 ms |
376 KB |
ok, correct split |
13 |
Correct |
2 ms |
380 KB |
ok, correct split |
14 |
Correct |
2 ms |
376 KB |
ok, correct split |
15 |
Correct |
155 ms |
17932 KB |
ok, correct split |
16 |
Correct |
146 ms |
14756 KB |
ok, correct split |
17 |
Correct |
125 ms |
20216 KB |
ok, correct split |
18 |
Correct |
127 ms |
19064 KB |
ok, correct split |
19 |
Correct |
177 ms |
16572 KB |
ok, correct split |
20 |
Correct |
131 ms |
14584 KB |
ok, correct split |
21 |
Correct |
109 ms |
15356 KB |
ok, correct split |
22 |
Correct |
115 ms |
15300 KB |
ok, correct split |
23 |
Correct |
99 ms |
15216 KB |
ok, correct split |
24 |
Correct |
2 ms |
376 KB |
ok, correct split |
25 |
Correct |
138 ms |
14616 KB |
ok, correct split |
26 |
Correct |
42 ms |
5876 KB |
ok, correct split |
27 |
Correct |
2 ms |
380 KB |
ok, correct split |
28 |
Correct |
185 ms |
17356 KB |
ok, correct split |
29 |
Correct |
142 ms |
17272 KB |
ok, correct split |
30 |
Correct |
186 ms |
17188 KB |
ok, correct split |
31 |
Correct |
174 ms |
17400 KB |
ok, correct split |
32 |
Correct |
220 ms |
17140 KB |
ok, correct split |
33 |
Correct |
54 ms |
4984 KB |
ok, no valid answer |
34 |
Correct |
81 ms |
7288 KB |
ok, no valid answer |
35 |
Correct |
198 ms |
14648 KB |
ok, no valid answer |
36 |
Correct |
201 ms |
14392 KB |
ok, no valid answer |
37 |
Correct |
185 ms |
14868 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
376 KB |
ok, correct split |
39 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
256 KB |
ok, correct split |
41 |
Correct |
2 ms |
256 KB |
ok, correct split |
42 |
Correct |
2 ms |
376 KB |
ok, correct split |
43 |
Correct |
2 ms |
376 KB |
ok, correct split |
44 |
Correct |
2 ms |
376 KB |
ok, correct split |
45 |
Correct |
2 ms |
376 KB |
ok, correct split |
46 |
Correct |
5 ms |
760 KB |
ok, correct split |
47 |
Correct |
5 ms |
764 KB |
ok, correct split |
48 |
Correct |
2 ms |
376 KB |
ok, correct split |
49 |
Correct |
5 ms |
760 KB |
ok, correct split |
50 |
Correct |
2 ms |
256 KB |
ok, correct split |
51 |
Correct |
2 ms |
256 KB |
ok, correct split |
52 |
Correct |
2 ms |
376 KB |
ok, correct split |
53 |
Correct |
2 ms |
376 KB |
ok, correct split |
54 |
Correct |
2 ms |
256 KB |
ok, correct split |
55 |
Correct |
2 ms |
256 KB |
ok, correct split |
56 |
Correct |
2 ms |
376 KB |
ok, correct split |
57 |
Correct |
4 ms |
548 KB |
ok, correct split |
58 |
Correct |
5 ms |
760 KB |
ok, correct split |
59 |
Correct |
4 ms |
764 KB |
ok, correct split |
60 |
Correct |
4 ms |
760 KB |
ok, correct split |
61 |
Correct |
4 ms |
760 KB |
ok, correct split |
62 |
Correct |
4 ms |
760 KB |
ok, correct split |
63 |
Incorrect |
5 ms |
760 KB |
jury found a solution, contestant did not |
64 |
Halted |
0 ms |
0 KB |
- |