#include "split.h"
#include <vector>
#include <utility>
#include <algorithm>
#define MAXN 100005
using namespace std;
int N, M, CanDo = 1, Done, Ans[MAXN], NodeType[MAXN];
int Size[MAXN], Lo[MAXN], Dep[MAXN], Par[MAXN];
pair <int,int> Days[3];
vector <int> adj[MAXN];
vector <pair<int,bool> > spT[MAXN]; //spanning tree rooted at 1
void dfs2(int u, int day, bool b) { //b = 1 means dfs on spanning tree
if (!Days[day].first || Ans[u]) {return;}
Ans[u] = Days[day].second;
Days[day].first--;
if (b) {
for (auto e: spT[u]) {
dfs2(e.first, day, b);
}
} else {
for (int v: adj[u]) {
dfs2(v, day, b);
}
}
}
void dfs(int u) {
if (Done) {return;}
Size[u] = 1;
Lo[u] = u;
bool AllSmall = 1;
int cutsize = 1;
for (int v: adj[u]) {
if (!Size[v]) {
Dep[v] = Dep[u] + 1;
Par[v] = u;
dfs(v);
if (Dep[Lo[v]] < Dep[Lo[u]]) {
Lo[u] = Lo[v];
}
AllSmall &= Size[v] < Days[0].first;
if (Lo[v] == v || Lo[v] == u) {
spT[u].push_back({v,1});
cutsize += Size[v];
} else {
spT[u].push_back({v,0});
}
Size[u] += Size[v];
} else if (v != Par[u] && Dep[v] < Dep[Lo[u]]) {
Lo[u] = v;
}
}
if (Size[u] >= Days[0].first && Size[u] <= N-Days[0].first) {
if (Size[u] >= Days[1].first) {
dfs2(u, 1, 1);
dfs2(Par[u], 0, 0);
} else {
dfs2(u,0, 1);
dfs2(Par[u],1, 0);
}
Done = true;
} else if ((Size[u] > N-Days[0].first) && AllSmall) {
if (cutsize > N-Days[0].first) {
//impossible
CanDo = 0;
} else {
//we got this
if (cutsize >= Days[1].first) {
Ans[u] = Days[1].second;
Days[1].first--;
for (auto e: spT[u]) {
if (e.second) {
dfs2(e.first, 1, 1);
}
}
dfs2(Par[u], 0, 0);
} else {
Ans[u] = Days[0].second;
Days[0].first--;
for (auto e: spT[u]) {
if (e.second) {
dfs2(e.first, 0, 1);
}
}
for (auto e: spT[u]) {
if (!e.second) {
dfs2(e.first, 0, 1);
}
}
dfs2(Par[u], 1, 0);
}
}
Done = true;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n, M = p.size(), Days[0].first = a, Days[1].first = b, Days[2].first = c;
for (int i=0; i<3; i++) {Days[i].second = i+1;}
sort(Days,Days+3);
for (int i=0; i<M; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(0);
vector <int> Out;
if (CanDo) {
for (int i=0; i < N; i++) {
if (Ans[i]) {
Out.push_back(Ans[i]);
} else {
Out.push_back(Days[2].second);
}
}
} else {
for (int i=0; i < N; i++) {
Out.push_back(0);
}
}
return(Out);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
4992 KB |
ok, correct split |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
3 ms |
4992 KB |
ok, correct split |
5 |
Correct |
3 ms |
5120 KB |
ok, correct split |
6 |
Correct |
4 ms |
5120 KB |
ok, correct split |
7 |
Correct |
134 ms |
25720 KB |
ok, correct split |
8 |
Correct |
87 ms |
16632 KB |
ok, correct split |
9 |
Correct |
94 ms |
19960 KB |
ok, correct split |
10 |
Correct |
119 ms |
25972 KB |
ok, correct split |
11 |
Correct |
119 ms |
26356 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
4992 KB |
ok, correct split |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
95 ms |
11764 KB |
ok, correct split |
5 |
Correct |
78 ms |
10968 KB |
ok, correct split |
6 |
Correct |
133 ms |
25972 KB |
ok, correct split |
7 |
Correct |
116 ms |
22776 KB |
ok, correct split |
8 |
Correct |
118 ms |
13600 KB |
ok, correct split |
9 |
Correct |
74 ms |
12536 KB |
ok, correct split |
10 |
Correct |
65 ms |
13036 KB |
ok, correct split |
11 |
Correct |
62 ms |
13000 KB |
ok, correct split |
12 |
Correct |
64 ms |
13036 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
117 ms |
14092 KB |
ok, correct split |
3 |
Correct |
28 ms |
8060 KB |
ok, correct split |
4 |
Correct |
4 ms |
4992 KB |
ok, correct split |
5 |
Correct |
120 ms |
17528 KB |
ok, correct split |
6 |
Correct |
100 ms |
16504 KB |
ok, correct split |
7 |
Correct |
114 ms |
17916 KB |
ok, correct split |
8 |
Correct |
114 ms |
20340 KB |
ok, correct split |
9 |
Correct |
116 ms |
18296 KB |
ok, correct split |
10 |
Correct |
28 ms |
8184 KB |
ok, no valid answer |
11 |
Correct |
42 ms |
9464 KB |
ok, no valid answer |
12 |
Correct |
79 ms |
13552 KB |
ok, no valid answer |
13 |
Correct |
93 ms |
13940 KB |
ok, no valid answer |
14 |
Correct |
65 ms |
13292 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
5024 KB |
ok, no valid answer |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
3 ms |
4992 KB |
ok, correct split |
5 |
Correct |
3 ms |
4992 KB |
ok, correct split |
6 |
Correct |
3 ms |
4992 KB |
ok, correct split |
7 |
Correct |
3 ms |
4992 KB |
ok, correct split |
8 |
Correct |
3 ms |
4992 KB |
ok, correct split |
9 |
Correct |
6 ms |
5376 KB |
ok, correct split |
10 |
Correct |
5 ms |
5248 KB |
ok, correct split |
11 |
Correct |
3 ms |
4992 KB |
ok, correct split |
12 |
Correct |
6 ms |
5376 KB |
ok, correct split |
13 |
Correct |
3 ms |
4992 KB |
ok, correct split |
14 |
Correct |
3 ms |
4992 KB |
ok, correct split |
15 |
Correct |
3 ms |
4992 KB |
ok, correct split |
16 |
Correct |
3 ms |
5024 KB |
ok, correct split |
17 |
Correct |
3 ms |
4992 KB |
ok, correct split |
18 |
Correct |
3 ms |
4992 KB |
ok, correct split |
19 |
Correct |
4 ms |
5120 KB |
ok, correct split |
20 |
Correct |
4 ms |
5120 KB |
ok, correct split |
21 |
Correct |
5 ms |
5376 KB |
ok, correct split |
22 |
Correct |
5 ms |
5376 KB |
ok, correct split |
23 |
Correct |
5 ms |
5376 KB |
ok, correct split |
24 |
Correct |
5 ms |
5376 KB |
ok, correct split |
25 |
Correct |
5 ms |
5376 KB |
ok, correct split |
26 |
Correct |
5 ms |
5248 KB |
ok, correct split |
27 |
Correct |
5 ms |
5248 KB |
ok, correct split |
28 |
Correct |
5 ms |
5248 KB |
ok, correct split |
29 |
Correct |
4 ms |
4992 KB |
ok, correct split |
30 |
Correct |
5 ms |
5376 KB |
ok, correct split |
31 |
Correct |
4 ms |
5120 KB |
ok, correct split |
32 |
Correct |
3 ms |
4992 KB |
ok, correct split |
33 |
Correct |
4 ms |
4992 KB |
ok, correct split |
34 |
Correct |
5 ms |
5248 KB |
ok, correct split |
35 |
Correct |
6 ms |
5248 KB |
ok, correct split |
36 |
Correct |
5 ms |
5248 KB |
ok, correct split |
37 |
Correct |
6 ms |
5376 KB |
ok, correct split |
38 |
Correct |
6 ms |
5376 KB |
ok, correct split |
39 |
Correct |
6 ms |
5376 KB |
ok, correct split |
40 |
Correct |
5 ms |
5376 KB |
ok, correct split |
41 |
Correct |
4 ms |
5120 KB |
ok, correct split |
42 |
Correct |
5 ms |
5120 KB |
ok, correct split |
43 |
Correct |
6 ms |
5376 KB |
ok, correct split |
44 |
Correct |
6 ms |
5376 KB |
ok, correct split |
45 |
Correct |
7 ms |
5376 KB |
ok, correct split |
46 |
Correct |
5 ms |
5376 KB |
ok, correct split |
47 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
48 |
Correct |
6 ms |
5248 KB |
ok, correct split |
49 |
Correct |
5 ms |
5504 KB |
ok, correct split |
50 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
51 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
52 |
Correct |
6 ms |
5248 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
5376 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
55 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
3 ms |
4992 KB |
ok, correct split |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
3 ms |
4992 KB |
ok, correct split |
5 |
Correct |
3 ms |
5120 KB |
ok, correct split |
6 |
Correct |
4 ms |
5120 KB |
ok, correct split |
7 |
Correct |
134 ms |
25720 KB |
ok, correct split |
8 |
Correct |
87 ms |
16632 KB |
ok, correct split |
9 |
Correct |
94 ms |
19960 KB |
ok, correct split |
10 |
Correct |
119 ms |
25972 KB |
ok, correct split |
11 |
Correct |
119 ms |
26356 KB |
ok, correct split |
12 |
Correct |
3 ms |
4992 KB |
ok, correct split |
13 |
Correct |
3 ms |
4992 KB |
ok, correct split |
14 |
Correct |
3 ms |
4992 KB |
ok, correct split |
15 |
Correct |
95 ms |
11764 KB |
ok, correct split |
16 |
Correct |
78 ms |
10968 KB |
ok, correct split |
17 |
Correct |
133 ms |
25972 KB |
ok, correct split |
18 |
Correct |
116 ms |
22776 KB |
ok, correct split |
19 |
Correct |
118 ms |
13600 KB |
ok, correct split |
20 |
Correct |
74 ms |
12536 KB |
ok, correct split |
21 |
Correct |
65 ms |
13036 KB |
ok, correct split |
22 |
Correct |
62 ms |
13000 KB |
ok, correct split |
23 |
Correct |
64 ms |
13036 KB |
ok, correct split |
24 |
Correct |
3 ms |
4992 KB |
ok, correct split |
25 |
Correct |
117 ms |
14092 KB |
ok, correct split |
26 |
Correct |
28 ms |
8060 KB |
ok, correct split |
27 |
Correct |
4 ms |
4992 KB |
ok, correct split |
28 |
Correct |
120 ms |
17528 KB |
ok, correct split |
29 |
Correct |
100 ms |
16504 KB |
ok, correct split |
30 |
Correct |
114 ms |
17916 KB |
ok, correct split |
31 |
Correct |
114 ms |
20340 KB |
ok, correct split |
32 |
Correct |
116 ms |
18296 KB |
ok, correct split |
33 |
Correct |
28 ms |
8184 KB |
ok, no valid answer |
34 |
Correct |
42 ms |
9464 KB |
ok, no valid answer |
35 |
Correct |
79 ms |
13552 KB |
ok, no valid answer |
36 |
Correct |
93 ms |
13940 KB |
ok, no valid answer |
37 |
Correct |
65 ms |
13292 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
4992 KB |
ok, correct split |
39 |
Correct |
3 ms |
5024 KB |
ok, no valid answer |
40 |
Correct |
3 ms |
4992 KB |
ok, correct split |
41 |
Correct |
3 ms |
4992 KB |
ok, correct split |
42 |
Correct |
3 ms |
4992 KB |
ok, correct split |
43 |
Correct |
3 ms |
4992 KB |
ok, correct split |
44 |
Correct |
3 ms |
4992 KB |
ok, correct split |
45 |
Correct |
3 ms |
4992 KB |
ok, correct split |
46 |
Correct |
6 ms |
5376 KB |
ok, correct split |
47 |
Correct |
5 ms |
5248 KB |
ok, correct split |
48 |
Correct |
3 ms |
4992 KB |
ok, correct split |
49 |
Correct |
6 ms |
5376 KB |
ok, correct split |
50 |
Correct |
3 ms |
4992 KB |
ok, correct split |
51 |
Correct |
3 ms |
4992 KB |
ok, correct split |
52 |
Correct |
3 ms |
4992 KB |
ok, correct split |
53 |
Correct |
3 ms |
5024 KB |
ok, correct split |
54 |
Correct |
3 ms |
4992 KB |
ok, correct split |
55 |
Correct |
3 ms |
4992 KB |
ok, correct split |
56 |
Correct |
4 ms |
5120 KB |
ok, correct split |
57 |
Correct |
4 ms |
5120 KB |
ok, correct split |
58 |
Correct |
5 ms |
5376 KB |
ok, correct split |
59 |
Correct |
5 ms |
5376 KB |
ok, correct split |
60 |
Correct |
5 ms |
5376 KB |
ok, correct split |
61 |
Correct |
5 ms |
5376 KB |
ok, correct split |
62 |
Correct |
5 ms |
5376 KB |
ok, correct split |
63 |
Correct |
5 ms |
5248 KB |
ok, correct split |
64 |
Correct |
5 ms |
5248 KB |
ok, correct split |
65 |
Correct |
5 ms |
5248 KB |
ok, correct split |
66 |
Correct |
4 ms |
4992 KB |
ok, correct split |
67 |
Correct |
5 ms |
5376 KB |
ok, correct split |
68 |
Correct |
4 ms |
5120 KB |
ok, correct split |
69 |
Correct |
3 ms |
4992 KB |
ok, correct split |
70 |
Correct |
4 ms |
4992 KB |
ok, correct split |
71 |
Correct |
5 ms |
5248 KB |
ok, correct split |
72 |
Correct |
6 ms |
5248 KB |
ok, correct split |
73 |
Correct |
5 ms |
5248 KB |
ok, correct split |
74 |
Correct |
6 ms |
5376 KB |
ok, correct split |
75 |
Correct |
6 ms |
5376 KB |
ok, correct split |
76 |
Correct |
6 ms |
5376 KB |
ok, correct split |
77 |
Correct |
5 ms |
5376 KB |
ok, correct split |
78 |
Correct |
4 ms |
5120 KB |
ok, correct split |
79 |
Correct |
5 ms |
5120 KB |
ok, correct split |
80 |
Correct |
6 ms |
5376 KB |
ok, correct split |
81 |
Correct |
6 ms |
5376 KB |
ok, correct split |
82 |
Correct |
7 ms |
5376 KB |
ok, correct split |
83 |
Correct |
5 ms |
5376 KB |
ok, correct split |
84 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
85 |
Correct |
6 ms |
5248 KB |
ok, correct split |
86 |
Correct |
5 ms |
5504 KB |
ok, correct split |
87 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
88 |
Correct |
3 ms |
4992 KB |
ok, no valid answer |
89 |
Correct |
6 ms |
5248 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
5376 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
5248 KB |
ok, no valid answer |
92 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
94 |
Correct |
141 ms |
19576 KB |
ok, correct split |
95 |
Correct |
185 ms |
25948 KB |
ok, correct split |
96 |
Correct |
163 ms |
23928 KB |
ok, correct split |
97 |
Correct |
29 ms |
8064 KB |
ok, correct split |
98 |
Correct |
32 ms |
8568 KB |
ok, correct split |
99 |
Correct |
60 ms |
12152 KB |
ok, correct split |
100 |
Correct |
119 ms |
17672 KB |
ok, correct split |
101 |
Correct |
108 ms |
16648 KB |
ok, correct split |
102 |
Correct |
104 ms |
16748 KB |
ok, correct split |
103 |
Correct |
95 ms |
15980 KB |
ok, correct split |
104 |
Correct |
123 ms |
18144 KB |
ok, correct split |
105 |
Correct |
57 ms |
11512 KB |
ok, correct split |
106 |
Correct |
127 ms |
17892 KB |
ok, correct split |
107 |
Correct |
106 ms |
15472 KB |
ok, correct split |
108 |
Correct |
115 ms |
15480 KB |
ok, correct split |
109 |
Correct |
167 ms |
18908 KB |
ok, correct split |
110 |
Correct |
166 ms |
19792 KB |
ok, correct split |
111 |
Correct |
151 ms |
19952 KB |
ok, correct split |
112 |
Correct |
152 ms |
18800 KB |
ok, correct split |
113 |
Correct |
150 ms |
18804 KB |
ok, correct split |
114 |
Correct |
16 ms |
6912 KB |
ok, correct split |
115 |
Correct |
15 ms |
6656 KB |
ok, correct split |
116 |
Correct |
147 ms |
19824 KB |
ok, correct split |
117 |
Correct |
162 ms |
19696 KB |
ok, correct split |
118 |
Correct |
112 ms |
16120 KB |
ok, correct split |
119 |
Correct |
81 ms |
13688 KB |
ok, correct split |
120 |
Correct |
112 ms |
20980 KB |
ok, correct split |
121 |
Correct |
109 ms |
15316 KB |
ok, no valid answer |
122 |
Correct |
112 ms |
14964 KB |
ok, no valid answer |
123 |
Correct |
168 ms |
19572 KB |
ok, no valid answer |
124 |
Correct |
167 ms |
19316 KB |
ok, no valid answer |
125 |
Correct |
93 ms |
15980 KB |
ok, no valid answer |
126 |
Correct |
57 ms |
13676 KB |
ok, no valid answer |
127 |
Correct |
113 ms |
17028 KB |
ok, no valid answer |