#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
//#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N;
vi adj[maxn],adj2[maxn],tree[maxn];
bool vis[maxn];
int sz[maxn];
void dfs(int x,int p){
vis[x] = 1;
sz[x] = 1;
aFOR(i, adj[x]) if (i != p && !vis[i]){
dfs(i,x);
sz[x] += sz[i];
tree[x].pb(i);
tree[i].pb(x);
}
}
int get_cent(int x,int p){
aFOR(i, tree[x]) if (i != p){
if (sz[i] > N / 2) return get_cent(i, x);
}
return x;
}
vi ans;
void assign(int x,int p,int v){
ans[x] = v;
aFOR(i, tree[x]) if (i != p) assign(i, x, v);
}
int grp[maxn];
void dfs2(int x,int p,int v){
grp[x] = v;
aFOR(i, tree[x]) if (i != p) dfs2(i,x,v);
}
int dfs3(int x){
vis[x] = 1;
int ans = sz[x];
aFOR(i, adj2[x]) if (!vis[i]){
ans += dfs3(i);
}
return ans;
}
int cur, cent;
void mark(int x){
vis[x] = 1;
cur -= sz[x];
assert(ans[x] == 2);
assign(x, cent, 1);
if (cur <= 0) return;
aFOR(i, adj2[x]) if (!vis[i] && cur > 0) mark(i);
}
void dfs4(int x,int y, int v){
if (cur < 0) return;
ans[x] = v;
cur--;
if (cur == 0) return;
aFOR(i,adj[x]) if (ans[i] == y && cur > 0) dfs4(i,y,v);
}
void get_sizes(int x,int p){
sz[x] = 1;
aFOR(i, tree[x]) if (i != p){
get_sizes(i, x); sz[x] += sz[i];
}
}
int m[3];
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n;
ans = vi(N,2);
FOR(i,0,p.size()-1){
adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]);
}
FOR(i,0,N-1) vis[i] = 0;
dfs(0,-1); // Get sizes rooted at 0 and spanning tree (Stored in tree array)
cent = get_cent(0, -1); // Get the centroid
vpi v;
v.pb(pi(a,1)); v.pb(pi(b, 2)); v.pb(pi(c,3));
sort(all(v));
get_sizes(cent, -1); // Change sz array to reflect sizes rooted at centroid
bool done = 0;
aFOR(i, tree[cent]){
assert(sz[i] <= N / 2);
if (sz[i] >= v[0].f){
assign(i, cent, 1); // If A can fit into a single component, set the entire thing to 1 first
//assert(sz[i] >= count(all(ans), 1));
done = 1; break;
}
}
if (!done){
aFOR(i, tree[cent]){
dfs2(i,cent,i); // Assign groups to each node
}
FOR(i,0,p.size()-1) if (p[i] != cent && q[i] != cent && grp[p[i]] != grp[q[i]]){ // Build graph between centroid sons
adj2[grp[p[i]]].pb(grp[q[i]]);
adj2[grp[q[i]]].pb(grp[p[i]]);
}
FOR(i,0,N-1) vis[i] = 0;
aFOR(i, tree[cent]){
int x = dfs3(i); // Get the total weight of the component under adj2
if (x >= v[0].f){
FOR(j,0,N-1) vis[j] = 0;
cur = v[0].f;
mark(i);
//assert(N - (v[0].f - cur) >= v[1].f);
//assert((v[0].f - cur) == count(all(ans), 1));
done = 1;
break;
}
}
}
if (!done) return vi(N,0);
//assert(count(all(ans), 1) >= v[0].f);
//assert(count(all(ans), 2) >= v[1].f);
FOR(i,1,2){
cur = v[i-1].f; if (cur == 0) continue;
int x = find(all(ans), i) - ans.begin();
dfs4(x,i,i+2);
}
FOR(i,0,N-1){
if (ans[i] < 3) ans[i] = 3;
else ans[i] -= 2;
ans[i] = v[ans[i]-1].s;
}
assert(count(all(ans), 1) == a);
assert(count(all(ans), 2) == b);
assert(count(all(ans), 3) == c);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
ok, correct split |
2 |
Correct |
7 ms |
14292 KB |
ok, correct split |
3 |
Correct |
7 ms |
14292 KB |
ok, correct split |
4 |
Correct |
7 ms |
14292 KB |
ok, correct split |
5 |
Correct |
7 ms |
14420 KB |
ok, correct split |
6 |
Correct |
7 ms |
14364 KB |
ok, correct split |
7 |
Correct |
88 ms |
32340 KB |
ok, correct split |
8 |
Correct |
81 ms |
29660 KB |
ok, correct split |
9 |
Correct |
86 ms |
28772 KB |
ok, correct split |
10 |
Correct |
86 ms |
32864 KB |
ok, correct split |
11 |
Correct |
89 ms |
32844 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14368 KB |
ok, correct split |
2 |
Correct |
7 ms |
14292 KB |
ok, correct split |
3 |
Correct |
7 ms |
14292 KB |
ok, correct split |
4 |
Correct |
103 ms |
28872 KB |
ok, correct split |
5 |
Correct |
78 ms |
23616 KB |
ok, correct split |
6 |
Correct |
80 ms |
32856 KB |
ok, correct split |
7 |
Correct |
90 ms |
29388 KB |
ok, correct split |
8 |
Correct |
112 ms |
25524 KB |
ok, correct split |
9 |
Correct |
86 ms |
23496 KB |
ok, correct split |
10 |
Correct |
56 ms |
24164 KB |
ok, correct split |
11 |
Correct |
68 ms |
24268 KB |
ok, correct split |
12 |
Correct |
60 ms |
24276 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14292 KB |
ok, correct split |
2 |
Correct |
81 ms |
23648 KB |
ok, correct split |
3 |
Correct |
40 ms |
18132 KB |
ok, correct split |
4 |
Correct |
8 ms |
14292 KB |
ok, correct split |
5 |
Correct |
96 ms |
26640 KB |
ok, correct split |
6 |
Correct |
87 ms |
26312 KB |
ok, correct split |
7 |
Correct |
92 ms |
26004 KB |
ok, correct split |
8 |
Correct |
89 ms |
27612 KB |
ok, correct split |
9 |
Correct |
86 ms |
25900 KB |
ok, correct split |
10 |
Correct |
27 ms |
17644 KB |
ok, no valid answer |
11 |
Correct |
39 ms |
19236 KB |
ok, no valid answer |
12 |
Correct |
70 ms |
24408 KB |
ok, no valid answer |
13 |
Correct |
80 ms |
24060 KB |
ok, no valid answer |
14 |
Correct |
60 ms |
24676 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
ok, correct split |
2 |
Correct |
8 ms |
14288 KB |
ok, no valid answer |
3 |
Correct |
7 ms |
14292 KB |
ok, correct split |
4 |
Correct |
7 ms |
14292 KB |
ok, correct split |
5 |
Correct |
8 ms |
14292 KB |
ok, correct split |
6 |
Correct |
8 ms |
14292 KB |
ok, correct split |
7 |
Correct |
8 ms |
14292 KB |
ok, correct split |
8 |
Correct |
7 ms |
14292 KB |
ok, correct split |
9 |
Correct |
10 ms |
14676 KB |
ok, correct split |
10 |
Correct |
10 ms |
14676 KB |
ok, correct split |
11 |
Correct |
7 ms |
14420 KB |
ok, correct split |
12 |
Correct |
9 ms |
14656 KB |
ok, correct split |
13 |
Correct |
7 ms |
14292 KB |
ok, correct split |
14 |
Correct |
7 ms |
14292 KB |
ok, correct split |
15 |
Correct |
8 ms |
14292 KB |
ok, correct split |
16 |
Correct |
7 ms |
14420 KB |
ok, correct split |
17 |
Correct |
7 ms |
14292 KB |
ok, correct split |
18 |
Correct |
8 ms |
14292 KB |
ok, correct split |
19 |
Correct |
8 ms |
14420 KB |
ok, correct split |
20 |
Correct |
8 ms |
14420 KB |
ok, correct split |
21 |
Correct |
9 ms |
14676 KB |
ok, correct split |
22 |
Correct |
10 ms |
14676 KB |
ok, correct split |
23 |
Correct |
9 ms |
14676 KB |
ok, correct split |
24 |
Correct |
9 ms |
14640 KB |
ok, correct split |
25 |
Correct |
8 ms |
14596 KB |
ok, correct split |
26 |
Correct |
9 ms |
14804 KB |
ok, correct split |
27 |
Correct |
10 ms |
14804 KB |
ok, correct split |
28 |
Correct |
10 ms |
14804 KB |
ok, correct split |
29 |
Correct |
8 ms |
14420 KB |
ok, correct split |
30 |
Correct |
9 ms |
14676 KB |
ok, correct split |
31 |
Correct |
9 ms |
14380 KB |
ok, correct split |
32 |
Correct |
7 ms |
14420 KB |
ok, correct split |
33 |
Correct |
8 ms |
14408 KB |
ok, correct split |
34 |
Correct |
10 ms |
14676 KB |
ok, correct split |
35 |
Correct |
9 ms |
14672 KB |
ok, correct split |
36 |
Correct |
9 ms |
14564 KB |
ok, correct split |
37 |
Correct |
10 ms |
14672 KB |
ok, correct split |
38 |
Correct |
9 ms |
14804 KB |
ok, correct split |
39 |
Correct |
10 ms |
14676 KB |
ok, correct split |
40 |
Correct |
10 ms |
14676 KB |
ok, correct split |
41 |
Correct |
8 ms |
14572 KB |
ok, correct split |
42 |
Correct |
8 ms |
14548 KB |
ok, correct split |
43 |
Correct |
10 ms |
14672 KB |
ok, correct split |
44 |
Correct |
10 ms |
14616 KB |
ok, correct split |
45 |
Correct |
10 ms |
14676 KB |
ok, correct split |
46 |
Correct |
9 ms |
14676 KB |
ok, correct split |
47 |
Correct |
9 ms |
14680 KB |
ok, no valid answer |
48 |
Correct |
9 ms |
14564 KB |
ok, correct split |
49 |
Correct |
8 ms |
14676 KB |
ok, correct split |
50 |
Correct |
10 ms |
14420 KB |
ok, no valid answer |
51 |
Correct |
8 ms |
14292 KB |
ok, no valid answer |
52 |
Correct |
9 ms |
14572 KB |
ok, no valid answer |
53 |
Correct |
9 ms |
14676 KB |
ok, no valid answer |
54 |
Correct |
9 ms |
14588 KB |
ok, no valid answer |
55 |
Correct |
9 ms |
14708 KB |
ok, no valid answer |
56 |
Correct |
9 ms |
14676 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
ok, correct split |
2 |
Correct |
7 ms |
14292 KB |
ok, correct split |
3 |
Correct |
7 ms |
14292 KB |
ok, correct split |
4 |
Correct |
7 ms |
14292 KB |
ok, correct split |
5 |
Correct |
7 ms |
14420 KB |
ok, correct split |
6 |
Correct |
7 ms |
14364 KB |
ok, correct split |
7 |
Correct |
88 ms |
32340 KB |
ok, correct split |
8 |
Correct |
81 ms |
29660 KB |
ok, correct split |
9 |
Correct |
86 ms |
28772 KB |
ok, correct split |
10 |
Correct |
86 ms |
32864 KB |
ok, correct split |
11 |
Correct |
89 ms |
32844 KB |
ok, correct split |
12 |
Correct |
8 ms |
14368 KB |
ok, correct split |
13 |
Correct |
7 ms |
14292 KB |
ok, correct split |
14 |
Correct |
7 ms |
14292 KB |
ok, correct split |
15 |
Correct |
103 ms |
28872 KB |
ok, correct split |
16 |
Correct |
78 ms |
23616 KB |
ok, correct split |
17 |
Correct |
80 ms |
32856 KB |
ok, correct split |
18 |
Correct |
90 ms |
29388 KB |
ok, correct split |
19 |
Correct |
112 ms |
25524 KB |
ok, correct split |
20 |
Correct |
86 ms |
23496 KB |
ok, correct split |
21 |
Correct |
56 ms |
24164 KB |
ok, correct split |
22 |
Correct |
68 ms |
24268 KB |
ok, correct split |
23 |
Correct |
60 ms |
24276 KB |
ok, correct split |
24 |
Correct |
7 ms |
14292 KB |
ok, correct split |
25 |
Correct |
81 ms |
23648 KB |
ok, correct split |
26 |
Correct |
40 ms |
18132 KB |
ok, correct split |
27 |
Correct |
8 ms |
14292 KB |
ok, correct split |
28 |
Correct |
96 ms |
26640 KB |
ok, correct split |
29 |
Correct |
87 ms |
26312 KB |
ok, correct split |
30 |
Correct |
92 ms |
26004 KB |
ok, correct split |
31 |
Correct |
89 ms |
27612 KB |
ok, correct split |
32 |
Correct |
86 ms |
25900 KB |
ok, correct split |
33 |
Correct |
27 ms |
17644 KB |
ok, no valid answer |
34 |
Correct |
39 ms |
19236 KB |
ok, no valid answer |
35 |
Correct |
70 ms |
24408 KB |
ok, no valid answer |
36 |
Correct |
80 ms |
24060 KB |
ok, no valid answer |
37 |
Correct |
60 ms |
24676 KB |
ok, no valid answer |
38 |
Correct |
8 ms |
14292 KB |
ok, correct split |
39 |
Correct |
8 ms |
14288 KB |
ok, no valid answer |
40 |
Correct |
7 ms |
14292 KB |
ok, correct split |
41 |
Correct |
7 ms |
14292 KB |
ok, correct split |
42 |
Correct |
8 ms |
14292 KB |
ok, correct split |
43 |
Correct |
8 ms |
14292 KB |
ok, correct split |
44 |
Correct |
8 ms |
14292 KB |
ok, correct split |
45 |
Correct |
7 ms |
14292 KB |
ok, correct split |
46 |
Correct |
10 ms |
14676 KB |
ok, correct split |
47 |
Correct |
10 ms |
14676 KB |
ok, correct split |
48 |
Correct |
7 ms |
14420 KB |
ok, correct split |
49 |
Correct |
9 ms |
14656 KB |
ok, correct split |
50 |
Correct |
7 ms |
14292 KB |
ok, correct split |
51 |
Correct |
7 ms |
14292 KB |
ok, correct split |
52 |
Correct |
8 ms |
14292 KB |
ok, correct split |
53 |
Correct |
7 ms |
14420 KB |
ok, correct split |
54 |
Correct |
7 ms |
14292 KB |
ok, correct split |
55 |
Correct |
8 ms |
14292 KB |
ok, correct split |
56 |
Correct |
8 ms |
14420 KB |
ok, correct split |
57 |
Correct |
8 ms |
14420 KB |
ok, correct split |
58 |
Correct |
9 ms |
14676 KB |
ok, correct split |
59 |
Correct |
10 ms |
14676 KB |
ok, correct split |
60 |
Correct |
9 ms |
14676 KB |
ok, correct split |
61 |
Correct |
9 ms |
14640 KB |
ok, correct split |
62 |
Correct |
8 ms |
14596 KB |
ok, correct split |
63 |
Correct |
9 ms |
14804 KB |
ok, correct split |
64 |
Correct |
10 ms |
14804 KB |
ok, correct split |
65 |
Correct |
10 ms |
14804 KB |
ok, correct split |
66 |
Correct |
8 ms |
14420 KB |
ok, correct split |
67 |
Correct |
9 ms |
14676 KB |
ok, correct split |
68 |
Correct |
9 ms |
14380 KB |
ok, correct split |
69 |
Correct |
7 ms |
14420 KB |
ok, correct split |
70 |
Correct |
8 ms |
14408 KB |
ok, correct split |
71 |
Correct |
10 ms |
14676 KB |
ok, correct split |
72 |
Correct |
9 ms |
14672 KB |
ok, correct split |
73 |
Correct |
9 ms |
14564 KB |
ok, correct split |
74 |
Correct |
10 ms |
14672 KB |
ok, correct split |
75 |
Correct |
9 ms |
14804 KB |
ok, correct split |
76 |
Correct |
10 ms |
14676 KB |
ok, correct split |
77 |
Correct |
10 ms |
14676 KB |
ok, correct split |
78 |
Correct |
8 ms |
14572 KB |
ok, correct split |
79 |
Correct |
8 ms |
14548 KB |
ok, correct split |
80 |
Correct |
10 ms |
14672 KB |
ok, correct split |
81 |
Correct |
10 ms |
14616 KB |
ok, correct split |
82 |
Correct |
10 ms |
14676 KB |
ok, correct split |
83 |
Correct |
9 ms |
14676 KB |
ok, correct split |
84 |
Correct |
9 ms |
14680 KB |
ok, no valid answer |
85 |
Correct |
9 ms |
14564 KB |
ok, correct split |
86 |
Correct |
8 ms |
14676 KB |
ok, correct split |
87 |
Correct |
10 ms |
14420 KB |
ok, no valid answer |
88 |
Correct |
8 ms |
14292 KB |
ok, no valid answer |
89 |
Correct |
9 ms |
14572 KB |
ok, no valid answer |
90 |
Correct |
9 ms |
14676 KB |
ok, no valid answer |
91 |
Correct |
9 ms |
14588 KB |
ok, no valid answer |
92 |
Correct |
9 ms |
14708 KB |
ok, no valid answer |
93 |
Correct |
9 ms |
14676 KB |
ok, no valid answer |
94 |
Correct |
97 ms |
28012 KB |
ok, correct split |
95 |
Correct |
131 ms |
33612 KB |
ok, correct split |
96 |
Correct |
118 ms |
31840 KB |
ok, correct split |
97 |
Correct |
32 ms |
18508 KB |
ok, correct split |
98 |
Correct |
34 ms |
18724 KB |
ok, correct split |
99 |
Correct |
52 ms |
21068 KB |
ok, correct split |
100 |
Correct |
118 ms |
28352 KB |
ok, correct split |
101 |
Correct |
103 ms |
27312 KB |
ok, correct split |
102 |
Correct |
105 ms |
26948 KB |
ok, correct split |
103 |
Correct |
93 ms |
26768 KB |
ok, correct split |
104 |
Correct |
93 ms |
28616 KB |
ok, correct split |
105 |
Correct |
59 ms |
21324 KB |
ok, correct split |
106 |
Correct |
110 ms |
32316 KB |
ok, correct split |
107 |
Correct |
85 ms |
25296 KB |
ok, correct split |
108 |
Correct |
86 ms |
25244 KB |
ok, correct split |
109 |
Correct |
124 ms |
28044 KB |
ok, correct split |
110 |
Correct |
123 ms |
29304 KB |
ok, correct split |
111 |
Correct |
145 ms |
29372 KB |
ok, correct split |
112 |
Correct |
131 ms |
29628 KB |
ok, correct split |
113 |
Correct |
122 ms |
29608 KB |
ok, correct split |
114 |
Correct |
16 ms |
16084 KB |
ok, correct split |
115 |
Correct |
16 ms |
15912 KB |
ok, correct split |
116 |
Correct |
116 ms |
29260 KB |
ok, correct split |
117 |
Correct |
112 ms |
29056 KB |
ok, correct split |
118 |
Correct |
102 ms |
24804 KB |
ok, correct split |
119 |
Correct |
86 ms |
24780 KB |
ok, correct split |
120 |
Correct |
89 ms |
29588 KB |
ok, correct split |
121 |
Correct |
78 ms |
25168 KB |
ok, no valid answer |
122 |
Correct |
75 ms |
25276 KB |
ok, no valid answer |
123 |
Correct |
119 ms |
29016 KB |
ok, no valid answer |
124 |
Correct |
114 ms |
28880 KB |
ok, no valid answer |
125 |
Correct |
79 ms |
26540 KB |
ok, no valid answer |
126 |
Correct |
54 ms |
24644 KB |
ok, no valid answer |
127 |
Correct |
85 ms |
26944 KB |
ok, no valid answer |