#include "split.h"
#include <bits/stdc++.h>
#define P(a) do{if(debug)cout<<a<<endl;} while(false);
#define H(a) P(#a<<": "<<a);
using namespace std;
const int inf = 2e9;
const bool debug = 0 ;
vector<vector<int> > graph;
vector<bool> vis1,vis2;
vector<int> ts,mi,res,size;
int t = 0;
int va,vb,vc;
int a,b,c;
int na = 0, nb = 0, nc = 0;
int n;
bool bol = false;
void dfs2(int u, int& mints);
void dfs3(int u);
int dfs(int u, int p){
if(vis1[u]) return 0;
if(ts[u]!=-1) return inf;
ts[u] = t++;
mi[u] = ts[u];
vis1[u] = true;
vector<int> cs;
int ma = 0;
for(int v : graph[u]) {
int s = dfs(v,u);
if(s!=inf){
size[u]+=s;
ma = max(ma,s);
}
if(v!=p) mi[u] = min(mi[u],mi[v]);
cs.push_back(s);
}
if(size[u]>=a && ma<a && !bol){
H(u);
H(size[u]);
H(ma);
P("a");
bol = true;
int p1 = size[u];
vector<int> startA;
for(int i = 0; i<graph[u].size(); i++){
H(cs[i]);
H(graph[u][i]);
H(mi[graph[u][i]]);
if(p1-cs[i]>=a&&mi[graph[u][i]]<ts[u]){
p1-=cs[i];
}
else if(ts[graph[u][i]] > ts[u]){
startA.push_back(graph[u][i]);
}
}
P(p1);
if(n-p1>=a){
if(p1>n-p1){
swap(a,b);
swap(va,vb);
}
na = 1;
vis2[u] = true;
res[u] = va;
for(int v : startA){
dfs2(v, ts[u]);
}
dfs3(0);
}
else{
res.assign(n,0);
}
}
vis1[u] = false;
return size[u];
}
void dfs2(int u, int& mints){
if(vis2[u] || ts[u] <mints || na >= a){
return;
}
vis2[u] = true;
res[u] = va;
na++;
for(int v : graph[u]){
dfs2(v, mints);
}
}
void dfs3(int u){
if(vis2[u] || nb>=b){
return;
}
vis2[u] = true;
res[u] = vb;
nb++;
for(int v : graph[u]){
dfs3(v);
}
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
pair<int,int> aa[3] = {{A,1}, {B,2}, {C,3}};
sort(aa, aa+3);
va = aa[0].second; vb = aa[1].second; vc = aa[2].second;
a = aa[0].first; b = aa[1].first; c = aa[2].first;
n = N;
graph.resize(n);
vis1.resize(n,0);
vis2.resize(n,0);
ts.resize(n,-1);
mi.resize(n,inf);
res.resize(n,vc);
size.resize(n,1);
for(int i = 0; i<p.size(); i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
dfs(0,0);
H(bol);
return res;
}
Compilation message
split.cpp: In function 'int dfs(int, int)':
split.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<graph[u].size(); i++){
~^~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<p.size(); i++){
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
ok, correct split |
2 |
Correct |
4 ms |
384 KB |
ok, correct split |
3 |
Correct |
4 ms |
384 KB |
ok, correct split |
4 |
Correct |
5 ms |
256 KB |
ok, correct split |
5 |
Correct |
5 ms |
384 KB |
ok, correct split |
6 |
Correct |
5 ms |
384 KB |
ok, correct split |
7 |
Correct |
123 ms |
26824 KB |
ok, correct split |
8 |
Correct |
126 ms |
21496 KB |
ok, correct split |
9 |
Correct |
116 ms |
19704 KB |
ok, correct split |
10 |
Correct |
120 ms |
27768 KB |
ok, correct split |
11 |
Correct |
136 ms |
27768 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
ok, correct split |
2 |
Correct |
4 ms |
256 KB |
ok, correct split |
3 |
Correct |
5 ms |
256 KB |
ok, correct split |
4 |
Correct |
139 ms |
18680 KB |
ok, correct split |
5 |
Correct |
99 ms |
9464 KB |
ok, correct split |
6 |
Correct |
114 ms |
27768 KB |
ok, correct split |
7 |
Correct |
135 ms |
22520 KB |
ok, correct split |
8 |
Correct |
164 ms |
11768 KB |
ok, correct split |
9 |
Correct |
99 ms |
9592 KB |
ok, correct split |
10 |
Correct |
65 ms |
10096 KB |
ok, correct split |
11 |
Correct |
67 ms |
10100 KB |
ok, correct split |
12 |
Correct |
68 ms |
10096 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
ok, correct split |
2 |
Correct |
98 ms |
9468 KB |
ok, correct split |
3 |
Correct |
34 ms |
4516 KB |
ok, correct split |
4 |
Correct |
5 ms |
256 KB |
ok, correct split |
5 |
Correct |
161 ms |
16352 KB |
ok, correct split |
6 |
Correct |
116 ms |
15736 KB |
ok, correct split |
7 |
Correct |
116 ms |
15352 KB |
ok, correct split |
8 |
Correct |
119 ms |
18552 KB |
ok, correct split |
9 |
Correct |
120 ms |
14968 KB |
ok, correct split |
10 |
Correct |
28 ms |
3712 KB |
ok, no valid answer |
11 |
Correct |
41 ms |
5496 KB |
ok, no valid answer |
12 |
Correct |
77 ms |
11124 KB |
ok, no valid answer |
13 |
Correct |
100 ms |
10700 KB |
ok, no valid answer |
14 |
Correct |
71 ms |
11632 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
ok, correct split |
2 |
Correct |
4 ms |
256 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
256 KB |
ok, correct split |
4 |
Correct |
4 ms |
256 KB |
ok, correct split |
5 |
Correct |
5 ms |
256 KB |
ok, correct split |
6 |
Correct |
5 ms |
256 KB |
ok, correct split |
7 |
Correct |
5 ms |
256 KB |
ok, correct split |
8 |
Correct |
4 ms |
256 KB |
ok, correct split |
9 |
Correct |
7 ms |
768 KB |
ok, correct split |
10 |
Correct |
7 ms |
640 KB |
ok, correct split |
11 |
Correct |
5 ms |
384 KB |
ok, correct split |
12 |
Correct |
7 ms |
640 KB |
ok, correct split |
13 |
Correct |
5 ms |
256 KB |
ok, correct split |
14 |
Correct |
5 ms |
384 KB |
ok, correct split |
15 |
Correct |
5 ms |
384 KB |
ok, correct split |
16 |
Correct |
4 ms |
384 KB |
ok, correct split |
17 |
Correct |
5 ms |
256 KB |
ok, correct split |
18 |
Correct |
5 ms |
256 KB |
ok, correct split |
19 |
Correct |
5 ms |
384 KB |
ok, correct split |
20 |
Correct |
5 ms |
512 KB |
ok, correct split |
21 |
Correct |
6 ms |
768 KB |
ok, correct split |
22 |
Correct |
6 ms |
640 KB |
ok, correct split |
23 |
Correct |
6 ms |
768 KB |
ok, correct split |
24 |
Correct |
6 ms |
768 KB |
ok, correct split |
25 |
Correct |
6 ms |
640 KB |
ok, correct split |
26 |
Correct |
7 ms |
640 KB |
ok, correct split |
27 |
Correct |
7 ms |
640 KB |
ok, correct split |
28 |
Correct |
7 ms |
640 KB |
ok, correct split |
29 |
Correct |
5 ms |
384 KB |
ok, correct split |
30 |
Correct |
7 ms |
640 KB |
ok, correct split |
31 |
Correct |
5 ms |
384 KB |
ok, correct split |
32 |
Correct |
5 ms |
384 KB |
ok, correct split |
33 |
Correct |
5 ms |
384 KB |
ok, correct split |
34 |
Correct |
6 ms |
640 KB |
ok, correct split |
35 |
Correct |
7 ms |
640 KB |
ok, correct split |
36 |
Correct |
6 ms |
640 KB |
ok, correct split |
37 |
Correct |
7 ms |
640 KB |
ok, correct split |
38 |
Correct |
7 ms |
768 KB |
ok, correct split |
39 |
Correct |
8 ms |
640 KB |
ok, correct split |
40 |
Correct |
7 ms |
640 KB |
ok, correct split |
41 |
Correct |
6 ms |
528 KB |
ok, correct split |
42 |
Correct |
6 ms |
512 KB |
ok, correct split |
43 |
Correct |
7 ms |
640 KB |
ok, correct split |
44 |
Correct |
7 ms |
712 KB |
ok, correct split |
45 |
Correct |
7 ms |
640 KB |
ok, correct split |
46 |
Correct |
7 ms |
768 KB |
ok, correct split |
47 |
Correct |
7 ms |
768 KB |
ok, no valid answer |
48 |
Correct |
7 ms |
640 KB |
ok, correct split |
49 |
Correct |
6 ms |
768 KB |
ok, correct split |
50 |
Correct |
5 ms |
256 KB |
ok, no valid answer |
51 |
Correct |
4 ms |
256 KB |
ok, no valid answer |
52 |
Correct |
7 ms |
512 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
640 KB |
ok, no valid answer |
54 |
Correct |
6 ms |
640 KB |
ok, no valid answer |
55 |
Correct |
8 ms |
640 KB |
ok, no valid answer |
56 |
Correct |
6 ms |
640 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
ok, correct split |
2 |
Correct |
4 ms |
384 KB |
ok, correct split |
3 |
Correct |
4 ms |
384 KB |
ok, correct split |
4 |
Correct |
5 ms |
256 KB |
ok, correct split |
5 |
Correct |
5 ms |
384 KB |
ok, correct split |
6 |
Correct |
5 ms |
384 KB |
ok, correct split |
7 |
Correct |
123 ms |
26824 KB |
ok, correct split |
8 |
Correct |
126 ms |
21496 KB |
ok, correct split |
9 |
Correct |
116 ms |
19704 KB |
ok, correct split |
10 |
Correct |
120 ms |
27768 KB |
ok, correct split |
11 |
Correct |
136 ms |
27768 KB |
ok, correct split |
12 |
Correct |
4 ms |
256 KB |
ok, correct split |
13 |
Correct |
4 ms |
256 KB |
ok, correct split |
14 |
Correct |
5 ms |
256 KB |
ok, correct split |
15 |
Correct |
139 ms |
18680 KB |
ok, correct split |
16 |
Correct |
99 ms |
9464 KB |
ok, correct split |
17 |
Correct |
114 ms |
27768 KB |
ok, correct split |
18 |
Correct |
135 ms |
22520 KB |
ok, correct split |
19 |
Correct |
164 ms |
11768 KB |
ok, correct split |
20 |
Correct |
99 ms |
9592 KB |
ok, correct split |
21 |
Correct |
65 ms |
10096 KB |
ok, correct split |
22 |
Correct |
67 ms |
10100 KB |
ok, correct split |
23 |
Correct |
68 ms |
10096 KB |
ok, correct split |
24 |
Correct |
5 ms |
384 KB |
ok, correct split |
25 |
Correct |
98 ms |
9468 KB |
ok, correct split |
26 |
Correct |
34 ms |
4516 KB |
ok, correct split |
27 |
Correct |
5 ms |
256 KB |
ok, correct split |
28 |
Correct |
161 ms |
16352 KB |
ok, correct split |
29 |
Correct |
116 ms |
15736 KB |
ok, correct split |
30 |
Correct |
116 ms |
15352 KB |
ok, correct split |
31 |
Correct |
119 ms |
18552 KB |
ok, correct split |
32 |
Correct |
120 ms |
14968 KB |
ok, correct split |
33 |
Correct |
28 ms |
3712 KB |
ok, no valid answer |
34 |
Correct |
41 ms |
5496 KB |
ok, no valid answer |
35 |
Correct |
77 ms |
11124 KB |
ok, no valid answer |
36 |
Correct |
100 ms |
10700 KB |
ok, no valid answer |
37 |
Correct |
71 ms |
11632 KB |
ok, no valid answer |
38 |
Correct |
5 ms |
256 KB |
ok, correct split |
39 |
Correct |
4 ms |
256 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
256 KB |
ok, correct split |
41 |
Correct |
4 ms |
256 KB |
ok, correct split |
42 |
Correct |
5 ms |
256 KB |
ok, correct split |
43 |
Correct |
5 ms |
256 KB |
ok, correct split |
44 |
Correct |
5 ms |
256 KB |
ok, correct split |
45 |
Correct |
4 ms |
256 KB |
ok, correct split |
46 |
Correct |
7 ms |
768 KB |
ok, correct split |
47 |
Correct |
7 ms |
640 KB |
ok, correct split |
48 |
Correct |
5 ms |
384 KB |
ok, correct split |
49 |
Correct |
7 ms |
640 KB |
ok, correct split |
50 |
Correct |
5 ms |
256 KB |
ok, correct split |
51 |
Correct |
5 ms |
384 KB |
ok, correct split |
52 |
Correct |
5 ms |
384 KB |
ok, correct split |
53 |
Correct |
4 ms |
384 KB |
ok, correct split |
54 |
Correct |
5 ms |
256 KB |
ok, correct split |
55 |
Correct |
5 ms |
256 KB |
ok, correct split |
56 |
Correct |
5 ms |
384 KB |
ok, correct split |
57 |
Correct |
5 ms |
512 KB |
ok, correct split |
58 |
Correct |
6 ms |
768 KB |
ok, correct split |
59 |
Correct |
6 ms |
640 KB |
ok, correct split |
60 |
Correct |
6 ms |
768 KB |
ok, correct split |
61 |
Correct |
6 ms |
768 KB |
ok, correct split |
62 |
Correct |
6 ms |
640 KB |
ok, correct split |
63 |
Correct |
7 ms |
640 KB |
ok, correct split |
64 |
Correct |
7 ms |
640 KB |
ok, correct split |
65 |
Correct |
7 ms |
640 KB |
ok, correct split |
66 |
Correct |
5 ms |
384 KB |
ok, correct split |
67 |
Correct |
7 ms |
640 KB |
ok, correct split |
68 |
Correct |
5 ms |
384 KB |
ok, correct split |
69 |
Correct |
5 ms |
384 KB |
ok, correct split |
70 |
Correct |
5 ms |
384 KB |
ok, correct split |
71 |
Correct |
6 ms |
640 KB |
ok, correct split |
72 |
Correct |
7 ms |
640 KB |
ok, correct split |
73 |
Correct |
6 ms |
640 KB |
ok, correct split |
74 |
Correct |
7 ms |
640 KB |
ok, correct split |
75 |
Correct |
7 ms |
768 KB |
ok, correct split |
76 |
Correct |
8 ms |
640 KB |
ok, correct split |
77 |
Correct |
7 ms |
640 KB |
ok, correct split |
78 |
Correct |
6 ms |
528 KB |
ok, correct split |
79 |
Correct |
6 ms |
512 KB |
ok, correct split |
80 |
Correct |
7 ms |
640 KB |
ok, correct split |
81 |
Correct |
7 ms |
712 KB |
ok, correct split |
82 |
Correct |
7 ms |
640 KB |
ok, correct split |
83 |
Correct |
7 ms |
768 KB |
ok, correct split |
84 |
Correct |
7 ms |
768 KB |
ok, no valid answer |
85 |
Correct |
7 ms |
640 KB |
ok, correct split |
86 |
Correct |
6 ms |
768 KB |
ok, correct split |
87 |
Correct |
5 ms |
256 KB |
ok, no valid answer |
88 |
Correct |
4 ms |
256 KB |
ok, no valid answer |
89 |
Correct |
7 ms |
512 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
640 KB |
ok, no valid answer |
91 |
Correct |
6 ms |
640 KB |
ok, no valid answer |
92 |
Correct |
8 ms |
640 KB |
ok, no valid answer |
93 |
Correct |
6 ms |
640 KB |
ok, no valid answer |
94 |
Correct |
124 ms |
16764 KB |
ok, correct split |
95 |
Correct |
189 ms |
24844 KB |
ok, correct split |
96 |
Correct |
162 ms |
22268 KB |
ok, correct split |
97 |
Correct |
34 ms |
4472 KB |
ok, correct split |
98 |
Correct |
36 ms |
4600 KB |
ok, correct split |
99 |
Correct |
62 ms |
8056 KB |
ok, correct split |
100 |
Correct |
183 ms |
14968 KB |
ok, correct split |
101 |
Correct |
141 ms |
13688 KB |
ok, correct split |
102 |
Correct |
128 ms |
13168 KB |
ok, correct split |
103 |
Correct |
114 ms |
12912 KB |
ok, correct split |
104 |
Correct |
133 ms |
14264 KB |
ok, correct split |
105 |
Correct |
56 ms |
6776 KB |
ok, correct split |
106 |
Correct |
138 ms |
14604 KB |
ok, correct split |
107 |
Correct |
97 ms |
10616 KB |
ok, correct split |
108 |
Correct |
102 ms |
10616 KB |
ok, correct split |
109 |
Correct |
153 ms |
13944 KB |
ok, correct split |
110 |
Correct |
149 ms |
14064 KB |
ok, correct split |
111 |
Correct |
158 ms |
14196 KB |
ok, correct split |
112 |
Correct |
146 ms |
14320 KB |
ok, correct split |
113 |
Correct |
147 ms |
14452 KB |
ok, correct split |
114 |
Correct |
19 ms |
2432 KB |
ok, correct split |
115 |
Correct |
17 ms |
2048 KB |
ok, correct split |
116 |
Correct |
140 ms |
14068 KB |
ok, correct split |
117 |
Correct |
138 ms |
14064 KB |
ok, correct split |
118 |
Correct |
103 ms |
10872 KB |
ok, correct split |
119 |
Correct |
95 ms |
10728 KB |
ok, correct split |
120 |
Correct |
117 ms |
20216 KB |
ok, correct split |
121 |
Correct |
89 ms |
10616 KB |
ok, no valid answer |
122 |
Correct |
86 ms |
10920 KB |
ok, no valid answer |
123 |
Correct |
199 ms |
15352 KB |
ok, no valid answer |
124 |
Correct |
154 ms |
15096 KB |
ok, no valid answer |
125 |
Correct |
94 ms |
12532 KB |
ok, no valid answer |
126 |
Correct |
62 ms |
10608 KB |
ok, no valid answer |
127 |
Correct |
136 ms |
13208 KB |
ok, no valid answer |