#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0',ch=getchar();}return s*f;}
#define re read()
const int mod = 1e9 + 7, MM = 1e5 + 5;
struct E{int u, v;}e[MM<<1], bad[MM<<1];
int N, tb, cnt, t, rt, id, sz[MM], dsu[MM], w[MM], vis[MM]; vector<int> s, adj[MM]; pair<int,int> ord[3];
int Find(int x){return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);}
void unite(int x, int y){x = Find(x), y = Find(y); sz[y] += sz[x], dsu[x] = y;}
int get_w(int src, int par){
w[src] = 1;
for (int v : adj[src])
if (v != par) w[src] += get_w(v, src);
return w[src];
}
int get_c(int src, int par){
for (int v : adj[src])
if (v != par && w[v] * 2 > N) return get_c(v, src);
return src;
}
void merge(int src, int par){
if (par != rt) unite(src, par);
for (int v : adj[src])
if (v != par) merge(v, src);
}
void paint(int src, int f){
if (s[src] || (!f && src == rt)) return;
// cout << src << ' ' << f << '\n';
vis[src] = 1, cnt ? (s[src] = ord[f].second, cnt--) : s[src] = ord[2].second;
for (int v : adj[src])
if (!vis[v]) paint(v, f);
}
vector<int> find_split(int n, int a, int b, int c, vector<int>p, vector<int>q){
int m = p.size(); s.resize(N = n);
for (int i = 0; i < m; i++) e[i] = {q[i], p[i]};
ord[0] = {a, 1}, ord[1] = {b, 2}, ord[2] = {c, 3};
sort(ord, ord + 3); iota(dsu, dsu + n, 0);
for (int i = 0; i < m; i++){
if (Find(e[i].v) != Find(e[i].u)){
unite(e[i].v, e[i].u);
adj[e[i].v].push_back(e[i].u), adj[e[i].u].push_back(e[i].v);
} else bad[tb++] = e[i];
} get_w(0, 0), rt = get_c(0, 0), iota(dsu, dsu + n, 0);
for (int i = 0; i < n; i++) sz[i] = 1;
for (int v : adj[rt]) merge(v, rt);
bool f = 0;
for (int v : adj[rt])
if (sz[Find(v)] >= ord[0].first) f = 1;
for (int i = 0; i < tb && !f; i++){
if (bad[i].u == rt || bad[i].v == rt) continue;
if (sz[Find(bad[i].u)] >= ord[0].first || sz[Find(bad[i].v)] >= ord[0].first) break;
if (Find(bad[i].u) != Find(bad[i].v)){
int v = bad[i].v, u = bad[i].u;
unite(u, v), adj[u].push_back(v); adj[v].push_back(u);
}
} id = -1;
for (int v : adj[rt])
if (sz[Find(v)] >= ord[0].first){id = v; break;}
// for (int i = 0; i < n; i++){
// cout << i << ": ";
// for (int v : adj[i]) cout << v << ' ';
// cout << '\n';
// }
if (id != -1){
cnt = ord[0].first, paint(id, 0), memset(vis, 0, sizeof vis);
cnt = ord[1].first, paint(rt, 1);
}
int cc[3] = {0};
for (int col = 0; col < 3; col++){
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; i++){
if (vis[i]) continue;
if (s[i] != ord[col].second) continue;
queue<int> q;
q.push(i);
vis[i] = 1;
int cnt = 0;
// cout << "col: " << col << '\n';
while(q.size()){
int u = q.front(); q.pop();
cnt++;
// cout << u << '\n';
for (int v : adj[u]){
if (!vis[v] && s[v] == ord[col].second)
vis[v] = 1, q.push(v);
}
}
// cout << col << ' ' << cnt << endl;
if (cnt == ord[col].first) cc[col] = 1;
}
}
// cout << cc << endl;
if (s[0]) assert(cc[1] && cc[0] );
return s;
}
// int main(){
// freopen("in.in", "r", stdin);
// int n, m, A, B, C;
// cin >> n >> m >> A >> B >> C;
// vector<int> a, b;
// for (int i = 0; i < m; i++){
// int x, y;
// cin >> x >> y;
// a.push_back(x), b.push_back(y);
// }
// vector<int> ans = find_split(n, A, B, C, a, b);
// for (int i= 0; i < n; i++){
// cout << i << ": " << ans[i] << '\n';
// }
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3020 KB |
ok, correct split |
2 |
Correct |
2 ms |
3020 KB |
ok, correct split |
3 |
Correct |
2 ms |
3020 KB |
ok, correct split |
4 |
Correct |
2 ms |
3020 KB |
ok, correct split |
5 |
Correct |
2 ms |
3020 KB |
ok, correct split |
6 |
Correct |
2 ms |
3020 KB |
ok, correct split |
7 |
Correct |
114 ms |
16360 KB |
ok, correct split |
8 |
Correct |
107 ms |
14532 KB |
ok, correct split |
9 |
Correct |
107 ms |
14056 KB |
ok, correct split |
10 |
Correct |
110 ms |
16488 KB |
ok, correct split |
11 |
Correct |
113 ms |
15468 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3020 KB |
ok, correct split |
2 |
Correct |
2 ms |
3020 KB |
ok, correct split |
3 |
Correct |
2 ms |
3020 KB |
ok, correct split |
4 |
Correct |
110 ms |
12020 KB |
ok, correct split |
5 |
Correct |
91 ms |
10480 KB |
ok, correct split |
6 |
Correct |
114 ms |
16604 KB |
ok, correct split |
7 |
Correct |
116 ms |
14568 KB |
ok, correct split |
8 |
Correct |
120 ms |
13380 KB |
ok, correct split |
9 |
Correct |
109 ms |
10480 KB |
ok, correct split |
10 |
Correct |
67 ms |
11068 KB |
ok, correct split |
11 |
Correct |
64 ms |
10988 KB |
ok, correct split |
12 |
Correct |
67 ms |
10988 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3020 KB |
ok, correct split |
2 |
Correct |
98 ms |
10604 KB |
ok, correct split |
3 |
Correct |
33 ms |
6044 KB |
ok, correct split |
4 |
Correct |
2 ms |
3020 KB |
ok, correct split |
5 |
Correct |
115 ms |
12612 KB |
ok, correct split |
6 |
Correct |
105 ms |
12304 KB |
ok, correct split |
7 |
Correct |
109 ms |
12100 KB |
ok, correct split |
8 |
Correct |
136 ms |
13204 KB |
ok, correct split |
9 |
Correct |
101 ms |
12072 KB |
ok, correct split |
10 |
Correct |
24 ms |
5492 KB |
ok, no valid answer |
11 |
Correct |
36 ms |
6724 KB |
ok, no valid answer |
12 |
Correct |
66 ms |
10688 KB |
ok, no valid answer |
13 |
Correct |
80 ms |
10608 KB |
ok, no valid answer |
14 |
Correct |
57 ms |
10856 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3020 KB |
ok, correct split |
2 |
Correct |
2 ms |
3020 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
3020 KB |
ok, correct split |
4 |
Correct |
2 ms |
3020 KB |
ok, correct split |
5 |
Correct |
2 ms |
3020 KB |
ok, correct split |
6 |
Correct |
2 ms |
3020 KB |
ok, correct split |
7 |
Correct |
2 ms |
3020 KB |
ok, correct split |
8 |
Correct |
2 ms |
3020 KB |
ok, correct split |
9 |
Correct |
4 ms |
3276 KB |
ok, correct split |
10 |
Correct |
4 ms |
3276 KB |
ok, correct split |
11 |
Correct |
2 ms |
3020 KB |
ok, correct split |
12 |
Correct |
4 ms |
3276 KB |
ok, correct split |
13 |
Correct |
2 ms |
3020 KB |
ok, correct split |
14 |
Correct |
2 ms |
3020 KB |
ok, correct split |
15 |
Correct |
2 ms |
3020 KB |
ok, correct split |
16 |
Correct |
2 ms |
3020 KB |
ok, correct split |
17 |
Correct |
2 ms |
2960 KB |
ok, correct split |
18 |
Correct |
2 ms |
3020 KB |
ok, correct split |
19 |
Correct |
2 ms |
3020 KB |
ok, correct split |
20 |
Correct |
3 ms |
3020 KB |
ok, correct split |
21 |
Correct |
4 ms |
3276 KB |
ok, correct split |
22 |
Correct |
3 ms |
3276 KB |
ok, correct split |
23 |
Correct |
4 ms |
3276 KB |
ok, correct split |
24 |
Correct |
4 ms |
3276 KB |
ok, correct split |
25 |
Correct |
3 ms |
3276 KB |
ok, correct split |
26 |
Correct |
4 ms |
3276 KB |
ok, correct split |
27 |
Correct |
4 ms |
3468 KB |
ok, correct split |
28 |
Correct |
4 ms |
3276 KB |
ok, correct split |
29 |
Correct |
2 ms |
3020 KB |
ok, correct split |
30 |
Correct |
4 ms |
3276 KB |
ok, correct split |
31 |
Correct |
3 ms |
3040 KB |
ok, correct split |
32 |
Correct |
2 ms |
3020 KB |
ok, correct split |
33 |
Correct |
2 ms |
3020 KB |
ok, correct split |
34 |
Correct |
4 ms |
3276 KB |
ok, correct split |
35 |
Correct |
4 ms |
3192 KB |
ok, correct split |
36 |
Correct |
4 ms |
3148 KB |
ok, correct split |
37 |
Correct |
4 ms |
3368 KB |
ok, correct split |
38 |
Correct |
5 ms |
3276 KB |
ok, correct split |
39 |
Correct |
4 ms |
3276 KB |
ok, correct split |
40 |
Correct |
4 ms |
3300 KB |
ok, correct split |
41 |
Correct |
3 ms |
3148 KB |
ok, correct split |
42 |
Correct |
3 ms |
3148 KB |
ok, correct split |
43 |
Correct |
4 ms |
3276 KB |
ok, correct split |
44 |
Correct |
4 ms |
3276 KB |
ok, correct split |
45 |
Correct |
4 ms |
3276 KB |
ok, correct split |
46 |
Correct |
4 ms |
3276 KB |
ok, correct split |
47 |
Correct |
4 ms |
3392 KB |
ok, no valid answer |
48 |
Correct |
4 ms |
3276 KB |
ok, correct split |
49 |
Correct |
4 ms |
3276 KB |
ok, correct split |
50 |
Correct |
2 ms |
3020 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
3020 KB |
ok, no valid answer |
52 |
Correct |
3 ms |
3276 KB |
ok, no valid answer |
53 |
Correct |
4 ms |
3276 KB |
ok, no valid answer |
54 |
Correct |
3 ms |
3276 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
3276 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
3304 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3020 KB |
ok, correct split |
2 |
Correct |
2 ms |
3020 KB |
ok, correct split |
3 |
Correct |
2 ms |
3020 KB |
ok, correct split |
4 |
Correct |
2 ms |
3020 KB |
ok, correct split |
5 |
Correct |
2 ms |
3020 KB |
ok, correct split |
6 |
Correct |
2 ms |
3020 KB |
ok, correct split |
7 |
Correct |
114 ms |
16360 KB |
ok, correct split |
8 |
Correct |
107 ms |
14532 KB |
ok, correct split |
9 |
Correct |
107 ms |
14056 KB |
ok, correct split |
10 |
Correct |
110 ms |
16488 KB |
ok, correct split |
11 |
Correct |
113 ms |
15468 KB |
ok, correct split |
12 |
Correct |
2 ms |
3020 KB |
ok, correct split |
13 |
Correct |
2 ms |
3020 KB |
ok, correct split |
14 |
Correct |
2 ms |
3020 KB |
ok, correct split |
15 |
Correct |
110 ms |
12020 KB |
ok, correct split |
16 |
Correct |
91 ms |
10480 KB |
ok, correct split |
17 |
Correct |
114 ms |
16604 KB |
ok, correct split |
18 |
Correct |
116 ms |
14568 KB |
ok, correct split |
19 |
Correct |
120 ms |
13380 KB |
ok, correct split |
20 |
Correct |
109 ms |
10480 KB |
ok, correct split |
21 |
Correct |
67 ms |
11068 KB |
ok, correct split |
22 |
Correct |
64 ms |
10988 KB |
ok, correct split |
23 |
Correct |
67 ms |
10988 KB |
ok, correct split |
24 |
Correct |
2 ms |
3020 KB |
ok, correct split |
25 |
Correct |
98 ms |
10604 KB |
ok, correct split |
26 |
Correct |
33 ms |
6044 KB |
ok, correct split |
27 |
Correct |
2 ms |
3020 KB |
ok, correct split |
28 |
Correct |
115 ms |
12612 KB |
ok, correct split |
29 |
Correct |
105 ms |
12304 KB |
ok, correct split |
30 |
Correct |
109 ms |
12100 KB |
ok, correct split |
31 |
Correct |
136 ms |
13204 KB |
ok, correct split |
32 |
Correct |
101 ms |
12072 KB |
ok, correct split |
33 |
Correct |
24 ms |
5492 KB |
ok, no valid answer |
34 |
Correct |
36 ms |
6724 KB |
ok, no valid answer |
35 |
Correct |
66 ms |
10688 KB |
ok, no valid answer |
36 |
Correct |
80 ms |
10608 KB |
ok, no valid answer |
37 |
Correct |
57 ms |
10856 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
3020 KB |
ok, correct split |
39 |
Correct |
2 ms |
3020 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
3020 KB |
ok, correct split |
41 |
Correct |
2 ms |
3020 KB |
ok, correct split |
42 |
Correct |
2 ms |
3020 KB |
ok, correct split |
43 |
Correct |
2 ms |
3020 KB |
ok, correct split |
44 |
Correct |
2 ms |
3020 KB |
ok, correct split |
45 |
Correct |
2 ms |
3020 KB |
ok, correct split |
46 |
Correct |
4 ms |
3276 KB |
ok, correct split |
47 |
Correct |
4 ms |
3276 KB |
ok, correct split |
48 |
Correct |
2 ms |
3020 KB |
ok, correct split |
49 |
Correct |
4 ms |
3276 KB |
ok, correct split |
50 |
Correct |
2 ms |
3020 KB |
ok, correct split |
51 |
Correct |
2 ms |
3020 KB |
ok, correct split |
52 |
Correct |
2 ms |
3020 KB |
ok, correct split |
53 |
Correct |
2 ms |
3020 KB |
ok, correct split |
54 |
Correct |
2 ms |
2960 KB |
ok, correct split |
55 |
Correct |
2 ms |
3020 KB |
ok, correct split |
56 |
Correct |
2 ms |
3020 KB |
ok, correct split |
57 |
Correct |
3 ms |
3020 KB |
ok, correct split |
58 |
Correct |
4 ms |
3276 KB |
ok, correct split |
59 |
Correct |
3 ms |
3276 KB |
ok, correct split |
60 |
Correct |
4 ms |
3276 KB |
ok, correct split |
61 |
Correct |
4 ms |
3276 KB |
ok, correct split |
62 |
Correct |
3 ms |
3276 KB |
ok, correct split |
63 |
Correct |
4 ms |
3276 KB |
ok, correct split |
64 |
Correct |
4 ms |
3468 KB |
ok, correct split |
65 |
Correct |
4 ms |
3276 KB |
ok, correct split |
66 |
Correct |
2 ms |
3020 KB |
ok, correct split |
67 |
Correct |
4 ms |
3276 KB |
ok, correct split |
68 |
Correct |
3 ms |
3040 KB |
ok, correct split |
69 |
Correct |
2 ms |
3020 KB |
ok, correct split |
70 |
Correct |
2 ms |
3020 KB |
ok, correct split |
71 |
Correct |
4 ms |
3276 KB |
ok, correct split |
72 |
Correct |
4 ms |
3192 KB |
ok, correct split |
73 |
Correct |
4 ms |
3148 KB |
ok, correct split |
74 |
Correct |
4 ms |
3368 KB |
ok, correct split |
75 |
Correct |
5 ms |
3276 KB |
ok, correct split |
76 |
Correct |
4 ms |
3276 KB |
ok, correct split |
77 |
Correct |
4 ms |
3300 KB |
ok, correct split |
78 |
Correct |
3 ms |
3148 KB |
ok, correct split |
79 |
Correct |
3 ms |
3148 KB |
ok, correct split |
80 |
Correct |
4 ms |
3276 KB |
ok, correct split |
81 |
Correct |
4 ms |
3276 KB |
ok, correct split |
82 |
Correct |
4 ms |
3276 KB |
ok, correct split |
83 |
Correct |
4 ms |
3276 KB |
ok, correct split |
84 |
Correct |
4 ms |
3392 KB |
ok, no valid answer |
85 |
Correct |
4 ms |
3276 KB |
ok, correct split |
86 |
Correct |
4 ms |
3276 KB |
ok, correct split |
87 |
Correct |
2 ms |
3020 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
3020 KB |
ok, no valid answer |
89 |
Correct |
3 ms |
3276 KB |
ok, no valid answer |
90 |
Correct |
4 ms |
3276 KB |
ok, no valid answer |
91 |
Correct |
3 ms |
3276 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
3276 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
3304 KB |
ok, no valid answer |
94 |
Correct |
100 ms |
12516 KB |
ok, correct split |
95 |
Correct |
129 ms |
15956 KB |
ok, correct split |
96 |
Correct |
118 ms |
14660 KB |
ok, correct split |
97 |
Correct |
33 ms |
6508 KB |
ok, correct split |
98 |
Correct |
33 ms |
6704 KB |
ok, correct split |
99 |
Correct |
44 ms |
8484 KB |
ok, correct split |
100 |
Correct |
132 ms |
15984 KB |
ok, correct split |
101 |
Correct |
114 ms |
14600 KB |
ok, correct split |
102 |
Correct |
105 ms |
14784 KB |
ok, correct split |
103 |
Correct |
105 ms |
14400 KB |
ok, correct split |
104 |
Correct |
102 ms |
16492 KB |
ok, correct split |
105 |
Correct |
51 ms |
8516 KB |
ok, correct split |
106 |
Correct |
101 ms |
16316 KB |
ok, correct split |
107 |
Correct |
109 ms |
11716 KB |
ok, correct split |
108 |
Correct |
92 ms |
11756 KB |
ok, correct split |
109 |
Correct |
142 ms |
15684 KB |
ok, correct split |
110 |
Correct |
140 ms |
16232 KB |
ok, correct split |
111 |
Correct |
132 ms |
16192 KB |
ok, correct split |
112 |
Correct |
132 ms |
16368 KB |
ok, correct split |
113 |
Correct |
130 ms |
16420 KB |
ok, correct split |
114 |
Correct |
12 ms |
4428 KB |
ok, correct split |
115 |
Correct |
12 ms |
4300 KB |
ok, correct split |
116 |
Correct |
116 ms |
15972 KB |
ok, correct split |
117 |
Correct |
116 ms |
15812 KB |
ok, correct split |
118 |
Correct |
101 ms |
11692 KB |
ok, correct split |
119 |
Correct |
97 ms |
11588 KB |
ok, correct split |
120 |
Correct |
114 ms |
14148 KB |
ok, correct split |
121 |
Correct |
78 ms |
11716 KB |
ok, no valid answer |
122 |
Correct |
74 ms |
11756 KB |
ok, no valid answer |
123 |
Correct |
110 ms |
15852 KB |
ok, no valid answer |
124 |
Correct |
118 ms |
15940 KB |
ok, no valid answer |
125 |
Correct |
76 ms |
13228 KB |
ok, no valid answer |
126 |
Correct |
50 ms |
11196 KB |
ok, no valid answer |
127 |
Correct |
86 ms |
14032 KB |
ok, no valid answer |