#include "split.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second
const int MAXN = 100010;
int n, top, sito, A, B, C, tm, tin[MAXN], low[MAXN], si[MAXN];
bool vis[MAXN], done;
vector<int> g[MAXN], tr[MAXN], ch;
int target, obt=1, roo2;
int ta2, ob2;
vector<int> res[3];
bool marked[MAXN], used[MAXN];
void dfs1(int v, int p){
si[v]=1;
vis[v]=true;
tin[v]=low[v]=tm++;
int forced=1;
bool atm=true;
vector<int> fset, rest;
for(int to:g[v]){
if(to==p) continue;
if(vis[to]){
low[v]=min(low[v], tin[to]);
}
else{
tr[v].PB(to);
dfs1(to, v);
si[v]+=si[to];
atm&=(si[to]<A);
low[v]=min(low[v], low[to]);
if(low[to]>=tin[v]){
forced+=si[to];
fset.PB(to);
}
else rest.PB(to);
}
}
if(atm && (si[v]>=A) && !done){
done = true;
roo2=p;
if(forced>n-A) top=-1;
else{
//assert(v!=0);
top=v;
sito=forced;
for(int el:fset) ch.PB(el);
while(sito<A){
ch.PB(rest.back());
sito+=si[rest.back()];
rest.pop_back();
}
}
}
}
void dfs2(int v){
if(obt<target){
used[v]=marked[v]=true;
res[0].PB(v);
++obt;
}
for(int to:tr[v]) dfs2(to);
}
void dfs3(int v){
vis[v]=true;
if(ob2<ta2){
++ob2;
used[v]=true;
res[1].PB(v);
}
for(int to:g[v]) if(!vis[to] && !marked[to]) dfs3(to);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n=N;
vector<pii> col = {{a, 0}, {b, 1}, {c, 2}};
sort(col.begin(), col.end());
A = col[0].F, B = col[1].F, C = col[2].F;
forn(i, p.size()){
g[p[i]].PB(q[i]);
g[q[i]].PB(p[i]);
}
dfs1(0, 0);
if(top==-1){
vector<int> ret(n, 0);
return ret;
}
if(sito>=B) target=B, ta2=A;
else target=A, ta2=B;
marked[top]=used[top]=true;
res[0].PB(top);
for(int el:ch) dfs2(el);
//assert((int)res[0].size() == target);
forn(i, n) vis[i]=false;
dfs3(roo2);
assert(res[1].size()==ta2);
if((int)res[0].size()==B) swap(res[0], res[1]);
forn(i, n) if(!used[i]) res[2].PB(i);
vector<int> ret(n);
forn(i, 3) for(int el:res[i]) ret[el]=col[i].S + 1;
return ret;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from split.cpp:5:
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:115:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
115 | assert(res[1].size()==ta2);
| ~~~~~~~~~~~~~^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
ok, correct split |
2 |
Correct |
2 ms |
4948 KB |
ok, correct split |
3 |
Correct |
3 ms |
4948 KB |
ok, correct split |
4 |
Correct |
2 ms |
4948 KB |
ok, correct split |
5 |
Correct |
2 ms |
4948 KB |
ok, correct split |
6 |
Correct |
2 ms |
4948 KB |
ok, correct split |
7 |
Correct |
117 ms |
33064 KB |
ok, correct split |
8 |
Correct |
96 ms |
27460 KB |
ok, correct split |
9 |
Correct |
75 ms |
25836 KB |
ok, correct split |
10 |
Correct |
88 ms |
33684 KB |
ok, correct split |
11 |
Correct |
78 ms |
33896 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
ok, correct split |
2 |
Correct |
2 ms |
4948 KB |
ok, correct split |
3 |
Correct |
3 ms |
4992 KB |
ok, correct split |
4 |
Correct |
104 ms |
23688 KB |
ok, correct split |
5 |
Correct |
51 ms |
13640 KB |
ok, correct split |
6 |
Correct |
86 ms |
33780 KB |
ok, correct split |
7 |
Correct |
87 ms |
27024 KB |
ok, correct split |
8 |
Correct |
79 ms |
16280 KB |
ok, correct split |
9 |
Correct |
63 ms |
15276 KB |
ok, correct split |
10 |
Correct |
34 ms |
12784 KB |
ok, correct split |
11 |
Correct |
34 ms |
12812 KB |
ok, correct split |
12 |
Correct |
53 ms |
12868 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
ok, correct split |
2 |
Correct |
69 ms |
13772 KB |
ok, correct split |
3 |
Correct |
22 ms |
9040 KB |
ok, correct split |
4 |
Correct |
3 ms |
5036 KB |
ok, correct split |
5 |
Correct |
66 ms |
22532 KB |
ok, correct split |
6 |
Correct |
63 ms |
22004 KB |
ok, correct split |
7 |
Correct |
64 ms |
21704 KB |
ok, correct split |
8 |
Correct |
93 ms |
24752 KB |
ok, correct split |
9 |
Correct |
63 ms |
21280 KB |
ok, correct split |
10 |
Correct |
17 ms |
8096 KB |
ok, no valid answer |
11 |
Correct |
22 ms |
9584 KB |
ok, no valid answer |
12 |
Correct |
43 ms |
13712 KB |
ok, no valid answer |
13 |
Correct |
65 ms |
14144 KB |
ok, no valid answer |
14 |
Correct |
35 ms |
13716 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
ok, correct split |
2 |
Correct |
2 ms |
4920 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
4948 KB |
ok, correct split |
4 |
Correct |
2 ms |
4948 KB |
ok, correct split |
5 |
Correct |
3 ms |
4948 KB |
ok, correct split |
6 |
Correct |
3 ms |
4948 KB |
ok, correct split |
7 |
Correct |
3 ms |
4948 KB |
ok, correct split |
8 |
Correct |
3 ms |
4948 KB |
ok, correct split |
9 |
Correct |
5 ms |
5460 KB |
ok, correct split |
10 |
Correct |
4 ms |
5204 KB |
ok, correct split |
11 |
Correct |
3 ms |
4948 KB |
ok, correct split |
12 |
Correct |
4 ms |
5332 KB |
ok, correct split |
13 |
Correct |
2 ms |
4948 KB |
ok, correct split |
14 |
Correct |
3 ms |
4948 KB |
ok, correct split |
15 |
Correct |
4 ms |
4948 KB |
ok, correct split |
16 |
Correct |
2 ms |
4948 KB |
ok, correct split |
17 |
Correct |
2 ms |
4948 KB |
ok, correct split |
18 |
Correct |
2 ms |
4948 KB |
ok, correct split |
19 |
Correct |
2 ms |
5076 KB |
ok, correct split |
20 |
Correct |
3 ms |
5204 KB |
ok, correct split |
21 |
Correct |
5 ms |
5352 KB |
ok, correct split |
22 |
Correct |
3 ms |
5332 KB |
ok, correct split |
23 |
Correct |
4 ms |
5448 KB |
ok, correct split |
24 |
Correct |
3 ms |
5332 KB |
ok, correct split |
25 |
Correct |
4 ms |
5332 KB |
ok, correct split |
26 |
Correct |
4 ms |
5204 KB |
ok, correct split |
27 |
Correct |
5 ms |
5204 KB |
ok, correct split |
28 |
Correct |
3 ms |
5204 KB |
ok, correct split |
29 |
Correct |
3 ms |
4948 KB |
ok, correct split |
30 |
Correct |
4 ms |
5204 KB |
ok, correct split |
31 |
Correct |
3 ms |
5076 KB |
ok, correct split |
32 |
Correct |
3 ms |
4948 KB |
ok, correct split |
33 |
Correct |
3 ms |
4948 KB |
ok, correct split |
34 |
Correct |
5 ms |
5204 KB |
ok, correct split |
35 |
Correct |
4 ms |
5204 KB |
ok, correct split |
36 |
Correct |
3 ms |
5204 KB |
ok, correct split |
37 |
Correct |
4 ms |
5332 KB |
ok, correct split |
38 |
Correct |
4 ms |
5332 KB |
ok, correct split |
39 |
Correct |
5 ms |
5204 KB |
ok, correct split |
40 |
Correct |
5 ms |
5204 KB |
ok, correct split |
41 |
Correct |
4 ms |
5076 KB |
ok, correct split |
42 |
Correct |
3 ms |
5076 KB |
ok, correct split |
43 |
Correct |
5 ms |
5332 KB |
ok, correct split |
44 |
Correct |
5 ms |
5332 KB |
ok, correct split |
45 |
Correct |
4 ms |
5332 KB |
ok, correct split |
46 |
Correct |
4 ms |
5460 KB |
ok, correct split |
47 |
Correct |
3 ms |
5332 KB |
ok, no valid answer |
48 |
Correct |
3 ms |
5280 KB |
ok, correct split |
49 |
Correct |
4 ms |
5460 KB |
ok, correct split |
50 |
Correct |
2 ms |
5008 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
4948 KB |
ok, no valid answer |
52 |
Correct |
4 ms |
5204 KB |
ok, no valid answer |
53 |
Correct |
4 ms |
5284 KB |
ok, no valid answer |
54 |
Correct |
4 ms |
5204 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
5220 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
5272 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
ok, correct split |
2 |
Correct |
2 ms |
4948 KB |
ok, correct split |
3 |
Correct |
3 ms |
4948 KB |
ok, correct split |
4 |
Correct |
2 ms |
4948 KB |
ok, correct split |
5 |
Correct |
2 ms |
4948 KB |
ok, correct split |
6 |
Correct |
2 ms |
4948 KB |
ok, correct split |
7 |
Correct |
117 ms |
33064 KB |
ok, correct split |
8 |
Correct |
96 ms |
27460 KB |
ok, correct split |
9 |
Correct |
75 ms |
25836 KB |
ok, correct split |
10 |
Correct |
88 ms |
33684 KB |
ok, correct split |
11 |
Correct |
78 ms |
33896 KB |
ok, correct split |
12 |
Correct |
2 ms |
4948 KB |
ok, correct split |
13 |
Correct |
2 ms |
4948 KB |
ok, correct split |
14 |
Correct |
3 ms |
4992 KB |
ok, correct split |
15 |
Correct |
104 ms |
23688 KB |
ok, correct split |
16 |
Correct |
51 ms |
13640 KB |
ok, correct split |
17 |
Correct |
86 ms |
33780 KB |
ok, correct split |
18 |
Correct |
87 ms |
27024 KB |
ok, correct split |
19 |
Correct |
79 ms |
16280 KB |
ok, correct split |
20 |
Correct |
63 ms |
15276 KB |
ok, correct split |
21 |
Correct |
34 ms |
12784 KB |
ok, correct split |
22 |
Correct |
34 ms |
12812 KB |
ok, correct split |
23 |
Correct |
53 ms |
12868 KB |
ok, correct split |
24 |
Correct |
3 ms |
4948 KB |
ok, correct split |
25 |
Correct |
69 ms |
13772 KB |
ok, correct split |
26 |
Correct |
22 ms |
9040 KB |
ok, correct split |
27 |
Correct |
3 ms |
5036 KB |
ok, correct split |
28 |
Correct |
66 ms |
22532 KB |
ok, correct split |
29 |
Correct |
63 ms |
22004 KB |
ok, correct split |
30 |
Correct |
64 ms |
21704 KB |
ok, correct split |
31 |
Correct |
93 ms |
24752 KB |
ok, correct split |
32 |
Correct |
63 ms |
21280 KB |
ok, correct split |
33 |
Correct |
17 ms |
8096 KB |
ok, no valid answer |
34 |
Correct |
22 ms |
9584 KB |
ok, no valid answer |
35 |
Correct |
43 ms |
13712 KB |
ok, no valid answer |
36 |
Correct |
65 ms |
14144 KB |
ok, no valid answer |
37 |
Correct |
35 ms |
13716 KB |
ok, no valid answer |
38 |
Correct |
3 ms |
4948 KB |
ok, correct split |
39 |
Correct |
2 ms |
4920 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
4948 KB |
ok, correct split |
41 |
Correct |
2 ms |
4948 KB |
ok, correct split |
42 |
Correct |
3 ms |
4948 KB |
ok, correct split |
43 |
Correct |
3 ms |
4948 KB |
ok, correct split |
44 |
Correct |
3 ms |
4948 KB |
ok, correct split |
45 |
Correct |
3 ms |
4948 KB |
ok, correct split |
46 |
Correct |
5 ms |
5460 KB |
ok, correct split |
47 |
Correct |
4 ms |
5204 KB |
ok, correct split |
48 |
Correct |
3 ms |
4948 KB |
ok, correct split |
49 |
Correct |
4 ms |
5332 KB |
ok, correct split |
50 |
Correct |
2 ms |
4948 KB |
ok, correct split |
51 |
Correct |
3 ms |
4948 KB |
ok, correct split |
52 |
Correct |
4 ms |
4948 KB |
ok, correct split |
53 |
Correct |
2 ms |
4948 KB |
ok, correct split |
54 |
Correct |
2 ms |
4948 KB |
ok, correct split |
55 |
Correct |
2 ms |
4948 KB |
ok, correct split |
56 |
Correct |
2 ms |
5076 KB |
ok, correct split |
57 |
Correct |
3 ms |
5204 KB |
ok, correct split |
58 |
Correct |
5 ms |
5352 KB |
ok, correct split |
59 |
Correct |
3 ms |
5332 KB |
ok, correct split |
60 |
Correct |
4 ms |
5448 KB |
ok, correct split |
61 |
Correct |
3 ms |
5332 KB |
ok, correct split |
62 |
Correct |
4 ms |
5332 KB |
ok, correct split |
63 |
Correct |
4 ms |
5204 KB |
ok, correct split |
64 |
Correct |
5 ms |
5204 KB |
ok, correct split |
65 |
Correct |
3 ms |
5204 KB |
ok, correct split |
66 |
Correct |
3 ms |
4948 KB |
ok, correct split |
67 |
Correct |
4 ms |
5204 KB |
ok, correct split |
68 |
Correct |
3 ms |
5076 KB |
ok, correct split |
69 |
Correct |
3 ms |
4948 KB |
ok, correct split |
70 |
Correct |
3 ms |
4948 KB |
ok, correct split |
71 |
Correct |
5 ms |
5204 KB |
ok, correct split |
72 |
Correct |
4 ms |
5204 KB |
ok, correct split |
73 |
Correct |
3 ms |
5204 KB |
ok, correct split |
74 |
Correct |
4 ms |
5332 KB |
ok, correct split |
75 |
Correct |
4 ms |
5332 KB |
ok, correct split |
76 |
Correct |
5 ms |
5204 KB |
ok, correct split |
77 |
Correct |
5 ms |
5204 KB |
ok, correct split |
78 |
Correct |
4 ms |
5076 KB |
ok, correct split |
79 |
Correct |
3 ms |
5076 KB |
ok, correct split |
80 |
Correct |
5 ms |
5332 KB |
ok, correct split |
81 |
Correct |
5 ms |
5332 KB |
ok, correct split |
82 |
Correct |
4 ms |
5332 KB |
ok, correct split |
83 |
Correct |
4 ms |
5460 KB |
ok, correct split |
84 |
Correct |
3 ms |
5332 KB |
ok, no valid answer |
85 |
Correct |
3 ms |
5280 KB |
ok, correct split |
86 |
Correct |
4 ms |
5460 KB |
ok, correct split |
87 |
Correct |
2 ms |
5008 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
4948 KB |
ok, no valid answer |
89 |
Correct |
4 ms |
5204 KB |
ok, no valid answer |
90 |
Correct |
4 ms |
5284 KB |
ok, no valid answer |
91 |
Correct |
4 ms |
5204 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
5220 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
5272 KB |
ok, no valid answer |
94 |
Correct |
70 ms |
21236 KB |
ok, correct split |
95 |
Correct |
134 ms |
30108 KB |
ok, correct split |
96 |
Correct |
90 ms |
27576 KB |
ok, correct split |
97 |
Correct |
20 ms |
9044 KB |
ok, correct split |
98 |
Correct |
22 ms |
9216 KB |
ok, correct split |
99 |
Correct |
32 ms |
13088 KB |
ok, correct split |
100 |
Correct |
123 ms |
19636 KB |
ok, correct split |
101 |
Correct |
71 ms |
18436 KB |
ok, correct split |
102 |
Correct |
65 ms |
17424 KB |
ok, correct split |
103 |
Correct |
61 ms |
17092 KB |
ok, correct split |
104 |
Correct |
57 ms |
17512 KB |
ok, correct split |
105 |
Correct |
32 ms |
11296 KB |
ok, correct split |
106 |
Correct |
62 ms |
17588 KB |
ok, correct split |
107 |
Correct |
61 ms |
14900 KB |
ok, correct split |
108 |
Correct |
52 ms |
14916 KB |
ok, correct split |
109 |
Correct |
79 ms |
18612 KB |
ok, correct split |
110 |
Correct |
82 ms |
19604 KB |
ok, correct split |
111 |
Correct |
92 ms |
19836 KB |
ok, correct split |
112 |
Correct |
71 ms |
18252 KB |
ok, correct split |
113 |
Correct |
74 ms |
18328 KB |
ok, correct split |
114 |
Correct |
13 ms |
7096 KB |
ok, correct split |
115 |
Correct |
9 ms |
6612 KB |
ok, correct split |
116 |
Correct |
100 ms |
19448 KB |
ok, correct split |
117 |
Correct |
76 ms |
19420 KB |
ok, correct split |
118 |
Correct |
72 ms |
16588 KB |
ok, correct split |
119 |
Correct |
56 ms |
16480 KB |
ok, correct split |
120 |
Correct |
72 ms |
26244 KB |
ok, correct split |
121 |
Correct |
47 ms |
14324 KB |
ok, no valid answer |
122 |
Correct |
48 ms |
14156 KB |
ok, no valid answer |
123 |
Correct |
102 ms |
19372 KB |
ok, no valid answer |
124 |
Correct |
74 ms |
19024 KB |
ok, no valid answer |
125 |
Correct |
45 ms |
15224 KB |
ok, no valid answer |
126 |
Correct |
47 ms |
13016 KB |
ok, no valid answer |
127 |
Correct |
70 ms |
16232 KB |
ok, no valid answer |