#include <bits/stdc++.h>
#include "split.h"
#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
const int MAXN = 1e5+10 ;
using namespace std ;
int A[3] , N ;
int sub[MAXN] , cor[MAXN] , pai[MAXN] , tam[MAXN] , idx[3] ;
vector<int> adj[MAXN] , tree[MAXN] ;
bool vis[MAXN] ;
vector<pii> outsideSt ;
bool ok = true ;
void findSt(int x, int d = -1 )
{
vis[x] = true ;
sub[x] = 1 ;
for(auto e : adj[x])
{
if(!vis[e])
{
tree[x].pb(e) ;
tree[e].pb(x) ;
findSt(e,x) ;
sub[x] += sub[e] ;
}
else if( e != d ) outsideSt.pb( mk(x,e) ) ;
}
}
void colore(int x, int pai, int c )
{
cor[x] = c ;
for(auto e : tree[x] )
if(pai != e) colore(e, x, c ) ;
}
int find(int x)
{
if(x == pai[x]) return x ;
return pai[x] = find(pai[x]) ;
}
int join(int x, int y)
{
x = find(x) ;
y = find(y) ;
if(x == y) return x ;
if(rand() % 2) swap(x,y) ;
pai[x] = y ;
tam[y] += tam[x] ;
return y;
}
void spin(int x)
{
int mx = -1 ;
for(auto e : tree[x] )
if( mx == -1 || sub[mx] < sub[e] ) mx = e ;
if( sub[mx] >= A[0] && (N-sub[mx]) >= A[0] )
{
if( sub[mx] > N-sub[mx] ) colore(mx, x, 1) ;
else colore(x, mx , 1) ;
}
else if( sub[mx] >= A[0] )
{
sub[x] = N - sub[mx] ;
sub[mx] = N ;
spin(mx) ;
}
else
{
for(int i = 1 ; i <= N ; i++ )
for(auto e : tree[i] )
{
if(i == x || e == x) continue ;
join(i, e) ;
}
for(auto e : outsideSt )
{
if(e.ff == x || e.ss == x) continue ;
int newPai = join(e.ff, e.ss );
if( tam[newPai] < A[0] ) continue ;
if( tam[newPai] > (N-tam[newPai]) )
{
for(int i = 1 ; i <= N ; i++ )
if( find(i) == newPai ) cor[i] = 1 ;
}
else
{
for(int i = 1 ; i <= N ; i++ )
if(find(i) != newPai ) cor[i] = 1 ;
}
return ;
}
ok = false ;
}
}
void pintando(int x, int y)
{
vis[x] = true ;
if( A[y] == 0 ) return ;
A[y]-- ;
for(auto e : adj[x] )
if(!vis[e] && cor[e] == y && A[y] ) pintando(e,y) ;
}
vector<int> find_split(int n , int a1 , int a2 , int a3 , vector<int> p ,vector<int> q )
{
A[0] = a1 ;
A[1] = a2 ;
A[2] = a3 ;
idx[0] = 0 ;
idx[1] = 1 ;
idx[2] = 2 ;
N = n ;
srand(time(0)) ;
sort(idx, idx+3 , [&](int i, int j) { return A[i] < A[j] ; } ) ;
sort(A, A+3) ;
lp(i,1,N+1) pai[i] = i , tam[i] = 1 ;
for(int i = 0 ; i < sz(p) ; i++ )
{
p[i]++ ;
q[i]++ ;
adj[ p[i] ].push_back(q[i]) ;
adj[ q[i] ].pb( p[i] ) ;
}
findSt(1) ;
spin(1) ;
lp(i,1,N+1) vis[i] = false ;
lp(i,1,N+1)
if(cor[i] == 0) { pintando(i,0) ; break ; }
lp(i,1,N+1)
if(cor[i] == 1) { pintando(i,1) ; break ; }
lp(i,1,N+1)
if(!vis[i]) cor[i] = 2 ;
vector<int> vec ;
if(!ok) idx[0] = idx[1] = idx[2] = -1 ;
for(int i = 0 ; i < N ; i++ ) vec.pb( idx[cor[i+1]] + 1 ) ;
return vec ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
4 ms |
4992 KB |
ok, correct split |
3 |
Correct |
4 ms |
4992 KB |
ok, correct split |
4 |
Correct |
3 ms |
5024 KB |
ok, correct split |
5 |
Correct |
3 ms |
4992 KB |
ok, correct split |
6 |
Correct |
3 ms |
4992 KB |
ok, correct split |
7 |
Correct |
138 ms |
22644 KB |
ok, correct split |
8 |
Correct |
126 ms |
20340 KB |
ok, correct split |
9 |
Correct |
140 ms |
19700 KB |
ok, correct split |
10 |
Correct |
130 ms |
23028 KB |
ok, correct split |
11 |
Correct |
142 ms |
23028 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 |
4 ms |
4992 KB |
ok, correct split |
4 |
Correct |
151 ms |
20924 KB |
ok, correct split |
5 |
Correct |
118 ms |
15352 KB |
ok, correct split |
6 |
Correct |
132 ms |
23028 KB |
ok, correct split |
7 |
Correct |
134 ms |
20084 KB |
ok, correct split |
8 |
Correct |
173 ms |
18928 KB |
ok, correct split |
9 |
Correct |
124 ms |
15220 KB |
ok, correct split |
10 |
Correct |
80 ms |
16112 KB |
ok, correct split |
11 |
Correct |
83 ms |
16112 KB |
ok, correct split |
12 |
Correct |
81 ms |
16180 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
ok, correct split |
2 |
Correct |
119 ms |
15340 KB |
ok, correct split |
3 |
Correct |
41 ms |
9336 KB |
ok, correct split |
4 |
Correct |
3 ms |
4992 KB |
ok, correct split |
5 |
Correct |
136 ms |
17764 KB |
ok, correct split |
6 |
Correct |
135 ms |
17524 KB |
ok, correct split |
7 |
Correct |
136 ms |
17268 KB |
ok, correct split |
8 |
Correct |
141 ms |
18804 KB |
ok, correct split |
9 |
Correct |
134 ms |
17140 KB |
ok, correct split |
10 |
Correct |
34 ms |
8704 KB |
ok, no valid answer |
11 |
Correct |
68 ms |
10360 KB |
ok, no valid answer |
12 |
Correct |
101 ms |
15732 KB |
ok, no valid answer |
13 |
Correct |
129 ms |
15480 KB |
ok, no valid answer |
14 |
Correct |
85 ms |
16112 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
4 ms |
4992 KB |
ok, no valid answer |
3 |
Correct |
4 ms |
4992 KB |
ok, correct split |
4 |
Correct |
4 ms |
4992 KB |
ok, correct split |
5 |
Correct |
4 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 |
4 ms |
4992 KB |
ok, correct split |
9 |
Correct |
6 ms |
5376 KB |
ok, correct split |
10 |
Correct |
6 ms |
5376 KB |
ok, correct split |
11 |
Correct |
4 ms |
5120 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 |
4992 KB |
ok, correct split |
17 |
Correct |
4 ms |
4992 KB |
ok, correct split |
18 |
Correct |
4 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 |
5504 KB |
ok, correct split |
23 |
Correct |
5 ms |
5376 KB |
ok, correct split |
24 |
Correct |
6 ms |
5376 KB |
ok, correct split |
25 |
Correct |
5 ms |
5376 KB |
ok, correct split |
26 |
Correct |
6 ms |
5376 KB |
ok, correct split |
27 |
Correct |
6 ms |
5376 KB |
ok, correct split |
28 |
Correct |
6 ms |
5376 KB |
ok, correct split |
29 |
Correct |
4 ms |
5120 KB |
ok, correct split |
30 |
Correct |
6 ms |
5376 KB |
ok, correct split |
31 |
Correct |
4 ms |
5120 KB |
ok, correct split |
32 |
Correct |
4 ms |
5120 KB |
ok, correct split |
33 |
Correct |
4 ms |
5120 KB |
ok, correct split |
34 |
Correct |
6 ms |
5376 KB |
ok, correct split |
35 |
Correct |
6 ms |
5376 KB |
ok, correct split |
36 |
Correct |
6 ms |
5376 KB |
ok, correct split |
37 |
Correct |
7 ms |
5504 KB |
ok, correct split |
38 |
Correct |
7 ms |
5504 KB |
ok, correct split |
39 |
Correct |
7 ms |
5504 KB |
ok, correct split |
40 |
Correct |
6 ms |
5504 KB |
ok, correct split |
41 |
Correct |
5 ms |
5248 KB |
ok, correct split |
42 |
Correct |
5 ms |
5248 KB |
ok, correct split |
43 |
Correct |
6 ms |
5504 KB |
ok, correct split |
44 |
Correct |
6 ms |
5504 KB |
ok, correct split |
45 |
Correct |
6 ms |
5504 KB |
ok, correct split |
46 |
Correct |
6 ms |
5376 KB |
ok, correct split |
47 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
48 |
Correct |
5 ms |
5376 KB |
ok, correct split |
49 |
Correct |
6 ms |
5504 KB |
ok, correct split |
50 |
Correct |
4 ms |
4992 KB |
ok, no valid answer |
51 |
Correct |
4 ms |
4992 KB |
ok, no valid answer |
52 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
5504 KB |
ok, no valid answer |
54 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
55 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
56 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4992 KB |
ok, correct split |
2 |
Correct |
4 ms |
4992 KB |
ok, correct split |
3 |
Correct |
4 ms |
4992 KB |
ok, correct split |
4 |
Correct |
3 ms |
5024 KB |
ok, correct split |
5 |
Correct |
3 ms |
4992 KB |
ok, correct split |
6 |
Correct |
3 ms |
4992 KB |
ok, correct split |
7 |
Correct |
138 ms |
22644 KB |
ok, correct split |
8 |
Correct |
126 ms |
20340 KB |
ok, correct split |
9 |
Correct |
140 ms |
19700 KB |
ok, correct split |
10 |
Correct |
130 ms |
23028 KB |
ok, correct split |
11 |
Correct |
142 ms |
23028 KB |
ok, correct split |
12 |
Correct |
3 ms |
4992 KB |
ok, correct split |
13 |
Correct |
3 ms |
4992 KB |
ok, correct split |
14 |
Correct |
4 ms |
4992 KB |
ok, correct split |
15 |
Correct |
151 ms |
20924 KB |
ok, correct split |
16 |
Correct |
118 ms |
15352 KB |
ok, correct split |
17 |
Correct |
132 ms |
23028 KB |
ok, correct split |
18 |
Correct |
134 ms |
20084 KB |
ok, correct split |
19 |
Correct |
173 ms |
18928 KB |
ok, correct split |
20 |
Correct |
124 ms |
15220 KB |
ok, correct split |
21 |
Correct |
80 ms |
16112 KB |
ok, correct split |
22 |
Correct |
83 ms |
16112 KB |
ok, correct split |
23 |
Correct |
81 ms |
16180 KB |
ok, correct split |
24 |
Correct |
4 ms |
4992 KB |
ok, correct split |
25 |
Correct |
119 ms |
15340 KB |
ok, correct split |
26 |
Correct |
41 ms |
9336 KB |
ok, correct split |
27 |
Correct |
3 ms |
4992 KB |
ok, correct split |
28 |
Correct |
136 ms |
17764 KB |
ok, correct split |
29 |
Correct |
135 ms |
17524 KB |
ok, correct split |
30 |
Correct |
136 ms |
17268 KB |
ok, correct split |
31 |
Correct |
141 ms |
18804 KB |
ok, correct split |
32 |
Correct |
134 ms |
17140 KB |
ok, correct split |
33 |
Correct |
34 ms |
8704 KB |
ok, no valid answer |
34 |
Correct |
68 ms |
10360 KB |
ok, no valid answer |
35 |
Correct |
101 ms |
15732 KB |
ok, no valid answer |
36 |
Correct |
129 ms |
15480 KB |
ok, no valid answer |
37 |
Correct |
85 ms |
16112 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
4992 KB |
ok, correct split |
39 |
Correct |
4 ms |
4992 KB |
ok, no valid answer |
40 |
Correct |
4 ms |
4992 KB |
ok, correct split |
41 |
Correct |
4 ms |
4992 KB |
ok, correct split |
42 |
Correct |
4 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 |
4 ms |
4992 KB |
ok, correct split |
46 |
Correct |
6 ms |
5376 KB |
ok, correct split |
47 |
Correct |
6 ms |
5376 KB |
ok, correct split |
48 |
Correct |
4 ms |
5120 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 |
4992 KB |
ok, correct split |
54 |
Correct |
4 ms |
4992 KB |
ok, correct split |
55 |
Correct |
4 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 |
5504 KB |
ok, correct split |
60 |
Correct |
5 ms |
5376 KB |
ok, correct split |
61 |
Correct |
6 ms |
5376 KB |
ok, correct split |
62 |
Correct |
5 ms |
5376 KB |
ok, correct split |
63 |
Correct |
6 ms |
5376 KB |
ok, correct split |
64 |
Correct |
6 ms |
5376 KB |
ok, correct split |
65 |
Correct |
6 ms |
5376 KB |
ok, correct split |
66 |
Correct |
4 ms |
5120 KB |
ok, correct split |
67 |
Correct |
6 ms |
5376 KB |
ok, correct split |
68 |
Correct |
4 ms |
5120 KB |
ok, correct split |
69 |
Correct |
4 ms |
5120 KB |
ok, correct split |
70 |
Correct |
4 ms |
5120 KB |
ok, correct split |
71 |
Correct |
6 ms |
5376 KB |
ok, correct split |
72 |
Correct |
6 ms |
5376 KB |
ok, correct split |
73 |
Correct |
6 ms |
5376 KB |
ok, correct split |
74 |
Correct |
7 ms |
5504 KB |
ok, correct split |
75 |
Correct |
7 ms |
5504 KB |
ok, correct split |
76 |
Correct |
7 ms |
5504 KB |
ok, correct split |
77 |
Correct |
6 ms |
5504 KB |
ok, correct split |
78 |
Correct |
5 ms |
5248 KB |
ok, correct split |
79 |
Correct |
5 ms |
5248 KB |
ok, correct split |
80 |
Correct |
6 ms |
5504 KB |
ok, correct split |
81 |
Correct |
6 ms |
5504 KB |
ok, correct split |
82 |
Correct |
6 ms |
5504 KB |
ok, correct split |
83 |
Correct |
6 ms |
5376 KB |
ok, correct split |
84 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
85 |
Correct |
5 ms |
5376 KB |
ok, correct split |
86 |
Correct |
6 ms |
5504 KB |
ok, correct split |
87 |
Correct |
4 ms |
4992 KB |
ok, no valid answer |
88 |
Correct |
4 ms |
4992 KB |
ok, no valid answer |
89 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
5504 KB |
ok, no valid answer |
91 |
Correct |
5 ms |
5376 KB |
ok, no valid answer |
92 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
93 |
Correct |
6 ms |
5376 KB |
ok, no valid answer |
94 |
Correct |
136 ms |
19696 KB |
ok, correct split |
95 |
Correct |
210 ms |
26168 KB |
ok, correct split |
96 |
Correct |
177 ms |
24040 KB |
ok, correct split |
97 |
Correct |
39 ms |
9720 KB |
ok, correct split |
98 |
Correct |
41 ms |
9976 KB |
ok, correct split |
99 |
Correct |
67 ms |
13676 KB |
ok, correct split |
100 |
Correct |
182 ms |
21864 KB |
ok, correct split |
101 |
Correct |
163 ms |
20328 KB |
ok, correct split |
102 |
Correct |
150 ms |
20072 KB |
ok, correct split |
103 |
Correct |
145 ms |
19652 KB |
ok, correct split |
104 |
Correct |
142 ms |
22104 KB |
ok, correct split |
105 |
Correct |
73 ms |
12312 KB |
ok, correct split |
106 |
Correct |
145 ms |
22340 KB |
ok, correct split |
107 |
Correct |
128 ms |
16628 KB |
ok, correct split |
108 |
Correct |
127 ms |
16500 KB |
ok, correct split |
109 |
Correct |
207 ms |
21104 KB |
ok, correct split |
110 |
Correct |
182 ms |
21224 KB |
ok, correct split |
111 |
Correct |
188 ms |
21352 KB |
ok, correct split |
112 |
Correct |
180 ms |
21608 KB |
ok, correct split |
113 |
Correct |
187 ms |
21608 KB |
ok, correct split |
114 |
Correct |
17 ms |
7164 KB |
ok, correct split |
115 |
Correct |
16 ms |
6908 KB |
ok, correct split |
116 |
Correct |
174 ms |
21224 KB |
ok, correct split |
117 |
Correct |
179 ms |
21096 KB |
ok, correct split |
118 |
Correct |
129 ms |
16372 KB |
ok, correct split |
119 |
Correct |
129 ms |
16368 KB |
ok, correct split |
120 |
Correct |
129 ms |
20468 KB |
ok, correct split |
121 |
Correct |
144 ms |
16504 KB |
ok, no valid answer |
122 |
Correct |
122 ms |
16628 KB |
ok, no valid answer |
123 |
Correct |
198 ms |
21984 KB |
ok, no valid answer |
124 |
Correct |
195 ms |
21876 KB |
ok, no valid answer |
125 |
Correct |
122 ms |
18548 KB |
ok, no valid answer |
126 |
Correct |
72 ms |
16112 KB |
ok, no valid answer |
127 |
Correct |
134 ms |
19308 KB |
ok, no valid answer |