#include "split.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
const int inf=1000001000; // 1e9
const ll INF=10000000010000000; // 1e16
const int mod=1000000007;
const int MAXN=100010;
vector<pair<int, char>> perm;
int n, m, k, a, b, c, u, v, t, x, y, solved;
int mark[MAXN], sz[MAXN], par[MAXN];
vector<int> G[MAXN];
vector<int> out;
int dfs1(int node){
mark[node]=1;
for (int v:G[node]) if (!mark[v]){
par[v]=node;
sz[node]+=dfs1(v);
}
return ++sz[node];
}
void dfs2(int node){
mark[node]=2;
for (int v:G[node]) if (mark[v]!=2) dfs2(v);
}
void dfs3(int node, vector<int> &topol){
mark[node]=3;
topol.pb(node);
for (int v:G[node]) if (mark[v]!=3 && par[v]==node) dfs3(v, topol);
}
vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){
n=_n;
out.resize(n, 0);
a=_a;
b=_b;
c=_c;
for (int i=0; i<SZ(_p); i++){
int u=_p[i], v=_q[i];
G[u].pb(v);
G[v].pb(u);
}
perm.pb({a, 'a'});
perm.pb({b, 'b'});
perm.pb({c, 'c'});
sort(all(perm));
a=perm[0].first;
b=perm[1].first;
c=perm[2].first;
vector<int> X, Y;
dfs1(0);
int v=0;
for (int i=1; i<n; i++) if (sz[i]>=a && sz[i]<sz[v]) v=i;
if (!v) return out; // -1
mark[v]=2;
dfs2(0);
mark[v]=3;
X.pb(v);
dfs3(0, Y);
int x=sz[v], y=n-x;
for (int u:G[v]) if (par[u]==v){
if (mark[u]!=2 || x-a<sz[u]) dfs3(u, X);
else{
x-=sz[u];
y+=sz[u];
dfs3(u, Y);
}
}
if (y>=b){
for (int i=0; i<a; i++) out[X[i]]=1;
for (int i=0; i<b; i++) out[Y[i]]=2;
solved=1;
}
else if (y>=a){
for (int i=0; i<a; i++) out[Y[i]]=1;
for (int i=0; i<b; i++) out[X[i]]=2;
solved=1;
}
if (!solved) return out;
for (int i=0; i<n; i++){
if (!out[i]) out[i]=3;
out[i]=perm[out[i]-1].second-'a'+1;
}
return out;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
ok, correct split |
2 |
Correct |
2 ms |
2636 KB |
ok, correct split |
3 |
Correct |
2 ms |
2636 KB |
ok, correct split |
4 |
Correct |
2 ms |
2636 KB |
ok, correct split |
5 |
Correct |
2 ms |
2636 KB |
ok, correct split |
6 |
Correct |
2 ms |
2636 KB |
ok, correct split |
7 |
Correct |
124 ms |
15924 KB |
ok, correct split |
8 |
Correct |
113 ms |
13896 KB |
ok, correct split |
9 |
Correct |
102 ms |
13380 KB |
ok, correct split |
10 |
Correct |
101 ms |
15940 KB |
ok, correct split |
11 |
Correct |
108 ms |
16160 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
ok, correct split |
2 |
Correct |
2 ms |
2636 KB |
ok, correct split |
3 |
Correct |
2 ms |
2636 KB |
ok, correct split |
4 |
Correct |
126 ms |
13796 KB |
ok, correct split |
5 |
Correct |
81 ms |
9876 KB |
ok, correct split |
6 |
Correct |
99 ms |
15972 KB |
ok, correct split |
7 |
Correct |
101 ms |
13764 KB |
ok, correct split |
8 |
Correct |
149 ms |
12192 KB |
ok, correct split |
9 |
Correct |
101 ms |
9808 KB |
ok, correct split |
10 |
Correct |
57 ms |
10188 KB |
ok, correct split |
11 |
Correct |
73 ms |
10184 KB |
ok, correct split |
12 |
Correct |
59 ms |
10176 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
ok, correct split |
2 |
Correct |
83 ms |
9904 KB |
ok, correct split |
3 |
Correct |
29 ms |
5660 KB |
ok, correct split |
4 |
Correct |
2 ms |
2636 KB |
ok, correct split |
5 |
Correct |
96 ms |
11844 KB |
ok, correct split |
6 |
Correct |
103 ms |
11632 KB |
ok, correct split |
7 |
Correct |
97 ms |
11484 KB |
ok, correct split |
8 |
Correct |
108 ms |
12720 KB |
ok, correct split |
9 |
Correct |
94 ms |
11324 KB |
ok, correct split |
10 |
Correct |
22 ms |
5068 KB |
ok, no valid answer |
11 |
Correct |
34 ms |
6320 KB |
ok, no valid answer |
12 |
Correct |
66 ms |
10176 KB |
ok, no valid answer |
13 |
Correct |
88 ms |
9924 KB |
ok, no valid answer |
14 |
Correct |
54 ms |
10148 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
ok, correct split |
2 |
Correct |
2 ms |
2636 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
2636 KB |
ok, correct split |
4 |
Correct |
2 ms |
2636 KB |
ok, correct split |
5 |
Correct |
2 ms |
2636 KB |
ok, correct split |
6 |
Correct |
2 ms |
2636 KB |
ok, correct split |
7 |
Correct |
2 ms |
2636 KB |
ok, correct split |
8 |
Correct |
2 ms |
2636 KB |
ok, correct split |
9 |
Correct |
4 ms |
2892 KB |
ok, correct split |
10 |
Correct |
4 ms |
2764 KB |
ok, correct split |
11 |
Correct |
2 ms |
2636 KB |
ok, correct split |
12 |
Correct |
4 ms |
2892 KB |
ok, correct split |
13 |
Correct |
2 ms |
2636 KB |
ok, correct split |
14 |
Correct |
2 ms |
2636 KB |
ok, correct split |
15 |
Correct |
2 ms |
2636 KB |
ok, correct split |
16 |
Correct |
2 ms |
2644 KB |
ok, correct split |
17 |
Correct |
2 ms |
2636 KB |
ok, correct split |
18 |
Correct |
2 ms |
2636 KB |
ok, correct split |
19 |
Correct |
2 ms |
2636 KB |
ok, correct split |
20 |
Correct |
3 ms |
2764 KB |
ok, correct split |
21 |
Correct |
4 ms |
2892 KB |
ok, correct split |
22 |
Correct |
3 ms |
2764 KB |
ok, correct split |
23 |
Correct |
3 ms |
2816 KB |
ok, correct split |
24 |
Correct |
4 ms |
2892 KB |
ok, correct split |
25 |
Correct |
3 ms |
2764 KB |
ok, correct split |
26 |
Correct |
4 ms |
2764 KB |
ok, correct split |
27 |
Correct |
5 ms |
2892 KB |
ok, correct split |
28 |
Correct |
4 ms |
2764 KB |
ok, correct split |
29 |
Correct |
2 ms |
2636 KB |
ok, correct split |
30 |
Correct |
5 ms |
2892 KB |
ok, correct split |
31 |
Correct |
2 ms |
2636 KB |
ok, correct split |
32 |
Correct |
2 ms |
2636 KB |
ok, correct split |
33 |
Correct |
2 ms |
2636 KB |
ok, correct split |
34 |
Correct |
3 ms |
2764 KB |
ok, correct split |
35 |
Correct |
4 ms |
2764 KB |
ok, correct split |
36 |
Correct |
4 ms |
2764 KB |
ok, correct split |
37 |
Correct |
4 ms |
2764 KB |
ok, correct split |
38 |
Correct |
4 ms |
2892 KB |
ok, correct split |
39 |
Correct |
5 ms |
2764 KB |
ok, correct split |
40 |
Correct |
4 ms |
2892 KB |
ok, correct split |
41 |
Correct |
3 ms |
2764 KB |
ok, correct split |
42 |
Correct |
3 ms |
2764 KB |
ok, correct split |
43 |
Correct |
4 ms |
2892 KB |
ok, correct split |
44 |
Correct |
4 ms |
2892 KB |
ok, correct split |
45 |
Correct |
4 ms |
2892 KB |
ok, correct split |
46 |
Correct |
3 ms |
2892 KB |
ok, correct split |
47 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
48 |
Correct |
4 ms |
2764 KB |
ok, correct split |
49 |
Correct |
3 ms |
2892 KB |
ok, correct split |
50 |
Correct |
2 ms |
2636 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
2636 KB |
ok, no valid answer |
52 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
53 |
Correct |
4 ms |
2892 KB |
ok, no valid answer |
54 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
55 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
56 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
ok, correct split |
2 |
Correct |
2 ms |
2636 KB |
ok, correct split |
3 |
Correct |
2 ms |
2636 KB |
ok, correct split |
4 |
Correct |
2 ms |
2636 KB |
ok, correct split |
5 |
Correct |
2 ms |
2636 KB |
ok, correct split |
6 |
Correct |
2 ms |
2636 KB |
ok, correct split |
7 |
Correct |
124 ms |
15924 KB |
ok, correct split |
8 |
Correct |
113 ms |
13896 KB |
ok, correct split |
9 |
Correct |
102 ms |
13380 KB |
ok, correct split |
10 |
Correct |
101 ms |
15940 KB |
ok, correct split |
11 |
Correct |
108 ms |
16160 KB |
ok, correct split |
12 |
Correct |
2 ms |
2636 KB |
ok, correct split |
13 |
Correct |
2 ms |
2636 KB |
ok, correct split |
14 |
Correct |
2 ms |
2636 KB |
ok, correct split |
15 |
Correct |
126 ms |
13796 KB |
ok, correct split |
16 |
Correct |
81 ms |
9876 KB |
ok, correct split |
17 |
Correct |
99 ms |
15972 KB |
ok, correct split |
18 |
Correct |
101 ms |
13764 KB |
ok, correct split |
19 |
Correct |
149 ms |
12192 KB |
ok, correct split |
20 |
Correct |
101 ms |
9808 KB |
ok, correct split |
21 |
Correct |
57 ms |
10188 KB |
ok, correct split |
22 |
Correct |
73 ms |
10184 KB |
ok, correct split |
23 |
Correct |
59 ms |
10176 KB |
ok, correct split |
24 |
Correct |
2 ms |
2636 KB |
ok, correct split |
25 |
Correct |
83 ms |
9904 KB |
ok, correct split |
26 |
Correct |
29 ms |
5660 KB |
ok, correct split |
27 |
Correct |
2 ms |
2636 KB |
ok, correct split |
28 |
Correct |
96 ms |
11844 KB |
ok, correct split |
29 |
Correct |
103 ms |
11632 KB |
ok, correct split |
30 |
Correct |
97 ms |
11484 KB |
ok, correct split |
31 |
Correct |
108 ms |
12720 KB |
ok, correct split |
32 |
Correct |
94 ms |
11324 KB |
ok, correct split |
33 |
Correct |
22 ms |
5068 KB |
ok, no valid answer |
34 |
Correct |
34 ms |
6320 KB |
ok, no valid answer |
35 |
Correct |
66 ms |
10176 KB |
ok, no valid answer |
36 |
Correct |
88 ms |
9924 KB |
ok, no valid answer |
37 |
Correct |
54 ms |
10148 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
2636 KB |
ok, correct split |
39 |
Correct |
2 ms |
2636 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
2636 KB |
ok, correct split |
41 |
Correct |
2 ms |
2636 KB |
ok, correct split |
42 |
Correct |
2 ms |
2636 KB |
ok, correct split |
43 |
Correct |
2 ms |
2636 KB |
ok, correct split |
44 |
Correct |
2 ms |
2636 KB |
ok, correct split |
45 |
Correct |
2 ms |
2636 KB |
ok, correct split |
46 |
Correct |
4 ms |
2892 KB |
ok, correct split |
47 |
Correct |
4 ms |
2764 KB |
ok, correct split |
48 |
Correct |
2 ms |
2636 KB |
ok, correct split |
49 |
Correct |
4 ms |
2892 KB |
ok, correct split |
50 |
Correct |
2 ms |
2636 KB |
ok, correct split |
51 |
Correct |
2 ms |
2636 KB |
ok, correct split |
52 |
Correct |
2 ms |
2636 KB |
ok, correct split |
53 |
Correct |
2 ms |
2644 KB |
ok, correct split |
54 |
Correct |
2 ms |
2636 KB |
ok, correct split |
55 |
Correct |
2 ms |
2636 KB |
ok, correct split |
56 |
Correct |
2 ms |
2636 KB |
ok, correct split |
57 |
Correct |
3 ms |
2764 KB |
ok, correct split |
58 |
Correct |
4 ms |
2892 KB |
ok, correct split |
59 |
Correct |
3 ms |
2764 KB |
ok, correct split |
60 |
Correct |
3 ms |
2816 KB |
ok, correct split |
61 |
Correct |
4 ms |
2892 KB |
ok, correct split |
62 |
Correct |
3 ms |
2764 KB |
ok, correct split |
63 |
Correct |
4 ms |
2764 KB |
ok, correct split |
64 |
Correct |
5 ms |
2892 KB |
ok, correct split |
65 |
Correct |
4 ms |
2764 KB |
ok, correct split |
66 |
Correct |
2 ms |
2636 KB |
ok, correct split |
67 |
Correct |
5 ms |
2892 KB |
ok, correct split |
68 |
Correct |
2 ms |
2636 KB |
ok, correct split |
69 |
Correct |
2 ms |
2636 KB |
ok, correct split |
70 |
Correct |
2 ms |
2636 KB |
ok, correct split |
71 |
Correct |
3 ms |
2764 KB |
ok, correct split |
72 |
Correct |
4 ms |
2764 KB |
ok, correct split |
73 |
Correct |
4 ms |
2764 KB |
ok, correct split |
74 |
Correct |
4 ms |
2764 KB |
ok, correct split |
75 |
Correct |
4 ms |
2892 KB |
ok, correct split |
76 |
Correct |
5 ms |
2764 KB |
ok, correct split |
77 |
Correct |
4 ms |
2892 KB |
ok, correct split |
78 |
Correct |
3 ms |
2764 KB |
ok, correct split |
79 |
Correct |
3 ms |
2764 KB |
ok, correct split |
80 |
Correct |
4 ms |
2892 KB |
ok, correct split |
81 |
Correct |
4 ms |
2892 KB |
ok, correct split |
82 |
Correct |
4 ms |
2892 KB |
ok, correct split |
83 |
Correct |
3 ms |
2892 KB |
ok, correct split |
84 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
85 |
Correct |
4 ms |
2764 KB |
ok, correct split |
86 |
Correct |
3 ms |
2892 KB |
ok, correct split |
87 |
Correct |
2 ms |
2636 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
2636 KB |
ok, no valid answer |
89 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
90 |
Correct |
4 ms |
2892 KB |
ok, no valid answer |
91 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
92 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
93 |
Correct |
3 ms |
2764 KB |
ok, no valid answer |
94 |
Correct |
101 ms |
12044 KB |
ok, correct split |
95 |
Correct |
150 ms |
16240 KB |
ok, correct split |
96 |
Correct |
131 ms |
14836 KB |
ok, correct split |
97 |
Correct |
28 ms |
5672 KB |
ok, correct split |
98 |
Correct |
33 ms |
5752 KB |
ok, correct split |
99 |
Correct |
47 ms |
7520 KB |
ok, correct split |
100 |
Correct |
134 ms |
12528 KB |
ok, correct split |
101 |
Correct |
121 ms |
11708 KB |
ok, correct split |
102 |
Correct |
125 ms |
11264 KB |
ok, correct split |
103 |
Correct |
99 ms |
11068 KB |
ok, correct split |
104 |
Correct |
99 ms |
12260 KB |
ok, correct split |
105 |
Correct |
45 ms |
7108 KB |
ok, correct split |
106 |
Correct |
98 ms |
12268 KB |
ok, correct split |
107 |
Correct |
88 ms |
10048 KB |
ok, correct split |
108 |
Correct |
88 ms |
9988 KB |
ok, correct split |
109 |
Correct |
130 ms |
12224 KB |
ok, correct split |
110 |
Correct |
128 ms |
11896 KB |
ok, correct split |
111 |
Correct |
134 ms |
11964 KB |
ok, correct split |
112 |
Correct |
122 ms |
12132 KB |
ok, correct split |
113 |
Correct |
143 ms |
12220 KB |
ok, correct split |
114 |
Correct |
12 ms |
3812 KB |
ok, correct split |
115 |
Correct |
11 ms |
3660 KB |
ok, correct split |
116 |
Correct |
137 ms |
11768 KB |
ok, correct split |
117 |
Correct |
166 ms |
11768 KB |
ok, correct split |
118 |
Correct |
97 ms |
9924 KB |
ok, correct split |
119 |
Correct |
88 ms |
9848 KB |
ok, correct split |
120 |
Correct |
105 ms |
13252 KB |
ok, correct split |
121 |
Correct |
82 ms |
9888 KB |
ok, no valid answer |
122 |
Correct |
70 ms |
9948 KB |
ok, no valid answer |
123 |
Correct |
128 ms |
12808 KB |
ok, no valid answer |
124 |
Correct |
125 ms |
12604 KB |
ok, no valid answer |
125 |
Correct |
74 ms |
10556 KB |
ok, no valid answer |
126 |
Correct |
51 ms |
9368 KB |
ok, no valid answer |
127 |
Correct |
86 ms |
10864 KB |
ok, no valid answer |