#include "bits/stdc++.h"
//#include "split.h"
using namespace std;
#define F first
#define S second
#define rep(i, n) for (int i = 1; i <= n; i++)
#define all(x) (x).begin(), (x).end()
#define comp(x) sort(all((x))); (x).erase(unique(all((x))), (x).end())
#define sz(x) (int)((x).size())
#define sq(x) (x) * (x)
#define srt(x) sort(all(x))
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define imp cout << "-1\n"
#define el cout << "\n"
const int MAX = 1e5 + 5;
const int LOG = 20;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dx[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
template<typename ...Args>
void read(Args&... args) { (cin >> ... >> args); }
struct Edge
{
int u, v;
};
class DisjointSet {
public:
DisjointSet(int n): n(n), par(n + 5), s(n + 5) {
init();
}
int n; vector<int> par, s;
void init(void)
{
iota(all(par), 0);
fill(all(s), 1);
}
int Find(int x)
{
if (x == par[x]) return x;
return par[x] = Find(par[x]);
}
bool Union(int p, int q)
{
p = Find(p); q = Find(q); if (p == q) return false;
par[q] = p; s[p] += s[q]; s[q] = 0; return true;
}
bool same(int p, int q)
{
p = Find(p); q = Find(q);
return (p == q);
}
int Size(int p)
{
p = Find(p);
return s[p];
}
};
const int NODE = 200005;
const int EDGE = 400005;
int n, m; vector<pi> abc(3);
// vi p(EDGE), q(EDGE);
vector<Edge> spantree, more;
DisjointSet ds(NODE);
vi adj[NODE], addadj[NODE], graph[NODE], szz(NODE);
vi ans;
int getSize(int node, int par)
{
szz[node] = 1;
for (auto &each : adj[node])
{
if (each == par) continue;
szz[node] += getSize(each, node);
}
return szz[node];
}
int getCent(int node, int par, int half)
{
for (auto &each : adj[node])
{
if (each == par) continue;
if (szz[each] > half) return getCent(each, node, half);
}
return node;
}
void ret(vi ans)
{
for (auto &each : ans) cout << each << ' ';
cout << '\n'; exit(0);
}
vi vst(NODE);
int cnt;
void dfsa(int node)
{
// cout << "node: " << node;
vst[node] = true;
cnt--;
if (cnt < 0) return;
ans[node] = abc[0].S;
// cout << "node: " << node << " - " << ans[node] << '\n';
for (auto &each : addadj[node])
{
if (vst[each]) continue;
dfsa(each);
}
}
void dfsb(int node)
{
cnt--;
if (cnt < 0) return;
ans[node] = abc[1].S;
// cout << "b: " << node << '\n';
for (auto &each : graph[node])
{
if (ans[each]) continue;
dfsb(each);
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
n = N; m = sz(p);
ans.resize(n);
abc[0].F = a; abc[1].F = b; abc[2].F = c;
for (int i = 0; i < 3; i++) abc[i].S = i + 1;
srt(abc);
for (int i = 0; i < m; i++)
{
graph[p[i]].pb(q[i]); graph[q[i]].pb(p[i]);
if (ds.Union(p[i], q[i]))
{
spantree.pb((Edge){ p[i], q[i] });
adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]);
}
else more.pb((Edge){ p[i], q[i] });
}
int limi = getSize(0, 0) / 2;
int cent = getCent(0, 0, limi);
// cout << "limit: " << limi << '\n';
// cout << "cent: " << cent << '\n';
for (int i = 0; i < n; i++)
{
for (auto &each : adj[i])
{
if (i == cent || each == cent) continue;
addadj[i].pb(each); addadj[each].pb(i);
}
}
ds.init();
for (auto &[u, v] : spantree)
{
if (u == cent || v == cent) continue;
ds.Union(u, v);
}
int anode = -1;
for (int i = 0; i < n; i++)
{
if (i == cent) continue;
if (ds.Size(i) >= abc[0].F)
{
anode = i;
break;
}
}
if (anode == -1)
{
for (auto &[u, v] : more)
{
if (u == cent || v == cent) continue;
ds.Union(u, v);
addadj[u].pb(v);
addadj[v].pb(u);
if (ds.Size(u) >= abc[0].F)
{
anode = u;
break;
}
}
}
if (anode == -1) return ans;
// cout << "anode: " << anode << '\n';
cnt = abc[0].F; vst[cent] = true;
dfsa(anode);
cnt = abc[1].F;
// cout << "bnum: " << cnt << '\n';
dfsb(cent);
for (int i = 0; i < n; i++) if (!ans[i]) ans[i] = abc[2].S;
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
17484 KB |
ok, correct split |
2 |
Correct |
10 ms |
17504 KB |
ok, correct split |
3 |
Correct |
10 ms |
17484 KB |
ok, correct split |
4 |
Correct |
10 ms |
17468 KB |
ok, correct split |
5 |
Correct |
10 ms |
17484 KB |
ok, correct split |
6 |
Correct |
10 ms |
17472 KB |
ok, correct split |
7 |
Correct |
162 ms |
37116 KB |
ok, correct split |
8 |
Correct |
134 ms |
35296 KB |
ok, correct split |
9 |
Correct |
144 ms |
34668 KB |
ok, correct split |
10 |
Correct |
215 ms |
37116 KB |
ok, correct split |
11 |
Correct |
158 ms |
36196 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
17484 KB |
ok, correct split |
2 |
Correct |
10 ms |
17484 KB |
ok, correct split |
3 |
Correct |
9 ms |
17484 KB |
ok, correct split |
4 |
Correct |
177 ms |
33900 KB |
ok, correct split |
5 |
Correct |
175 ms |
32056 KB |
ok, correct split |
6 |
Correct |
143 ms |
37104 KB |
ok, correct split |
7 |
Correct |
150 ms |
35140 KB |
ok, correct split |
8 |
Correct |
205 ms |
35640 KB |
ok, correct split |
9 |
Correct |
142 ms |
31216 KB |
ok, correct split |
10 |
Correct |
85 ms |
28384 KB |
ok, correct split |
11 |
Correct |
84 ms |
28464 KB |
ok, correct split |
12 |
Correct |
77 ms |
28768 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
17484 KB |
ok, correct split |
2 |
Correct |
202 ms |
31096 KB |
ok, correct split |
3 |
Correct |
46 ms |
23044 KB |
ok, correct split |
4 |
Correct |
9 ms |
17484 KB |
ok, correct split |
5 |
Correct |
146 ms |
32224 KB |
ok, correct split |
6 |
Correct |
194 ms |
32060 KB |
ok, correct split |
7 |
Correct |
146 ms |
31800 KB |
ok, correct split |
8 |
Correct |
143 ms |
32880 KB |
ok, correct split |
9 |
Correct |
146 ms |
31712 KB |
ok, correct split |
10 |
Correct |
60 ms |
22124 KB |
ok, no valid answer |
11 |
Correct |
60 ms |
24252 KB |
ok, no valid answer |
12 |
Correct |
106 ms |
29092 KB |
ok, no valid answer |
13 |
Correct |
139 ms |
30776 KB |
ok, no valid answer |
14 |
Correct |
110 ms |
27792 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
17536 KB |
ok, correct split |
2 |
Correct |
10 ms |
17484 KB |
ok, no valid answer |
3 |
Correct |
10 ms |
17512 KB |
ok, correct split |
4 |
Correct |
10 ms |
17536 KB |
ok, correct split |
5 |
Correct |
10 ms |
17484 KB |
ok, correct split |
6 |
Correct |
10 ms |
17528 KB |
ok, correct split |
7 |
Correct |
10 ms |
17484 KB |
ok, correct split |
8 |
Correct |
10 ms |
17440 KB |
ok, correct split |
9 |
Correct |
14 ms |
17936 KB |
ok, correct split |
10 |
Correct |
12 ms |
17848 KB |
ok, correct split |
11 |
Correct |
10 ms |
17540 KB |
ok, correct split |
12 |
Correct |
13 ms |
17932 KB |
ok, correct split |
13 |
Correct |
10 ms |
17484 KB |
ok, correct split |
14 |
Correct |
10 ms |
17484 KB |
ok, correct split |
15 |
Correct |
10 ms |
17532 KB |
ok, correct split |
16 |
Correct |
10 ms |
17532 KB |
ok, correct split |
17 |
Correct |
10 ms |
17484 KB |
ok, correct split |
18 |
Correct |
9 ms |
17540 KB |
ok, correct split |
19 |
Correct |
10 ms |
17552 KB |
ok, correct split |
20 |
Correct |
11 ms |
17688 KB |
ok, correct split |
21 |
Correct |
12 ms |
17836 KB |
ok, correct split |
22 |
Correct |
12 ms |
17844 KB |
ok, correct split |
23 |
Correct |
15 ms |
17868 KB |
ok, correct split |
24 |
Correct |
15 ms |
17800 KB |
ok, correct split |
25 |
Correct |
11 ms |
17784 KB |
ok, correct split |
26 |
Correct |
12 ms |
17868 KB |
ok, correct split |
27 |
Correct |
12 ms |
17936 KB |
ok, correct split |
28 |
Correct |
13 ms |
17856 KB |
ok, correct split |
29 |
Correct |
11 ms |
17548 KB |
ok, correct split |
30 |
Correct |
12 ms |
17916 KB |
ok, correct split |
31 |
Correct |
11 ms |
17612 KB |
ok, correct split |
32 |
Correct |
11 ms |
17532 KB |
ok, correct split |
33 |
Correct |
10 ms |
17548 KB |
ok, correct split |
34 |
Correct |
11 ms |
17840 KB |
ok, correct split |
35 |
Correct |
12 ms |
17860 KB |
ok, correct split |
36 |
Correct |
11 ms |
17812 KB |
ok, correct split |
37 |
Correct |
15 ms |
17864 KB |
ok, correct split |
38 |
Correct |
13 ms |
17996 KB |
ok, correct split |
39 |
Correct |
16 ms |
17996 KB |
ok, correct split |
40 |
Correct |
13 ms |
17936 KB |
ok, correct split |
41 |
Correct |
11 ms |
17740 KB |
ok, correct split |
42 |
Correct |
11 ms |
17640 KB |
ok, correct split |
43 |
Correct |
13 ms |
17868 KB |
ok, correct split |
44 |
Correct |
12 ms |
17860 KB |
ok, correct split |
45 |
Correct |
12 ms |
17932 KB |
ok, correct split |
46 |
Correct |
11 ms |
17868 KB |
ok, correct split |
47 |
Correct |
12 ms |
17820 KB |
ok, no valid answer |
48 |
Correct |
14 ms |
17800 KB |
ok, correct split |
49 |
Correct |
11 ms |
17820 KB |
ok, correct split |
50 |
Correct |
9 ms |
17484 KB |
ok, no valid answer |
51 |
Correct |
9 ms |
17528 KB |
ok, no valid answer |
52 |
Correct |
11 ms |
17800 KB |
ok, no valid answer |
53 |
Correct |
12 ms |
17928 KB |
ok, no valid answer |
54 |
Correct |
11 ms |
17740 KB |
ok, no valid answer |
55 |
Correct |
11 ms |
17860 KB |
ok, no valid answer |
56 |
Correct |
15 ms |
17920 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
17484 KB |
ok, correct split |
2 |
Correct |
10 ms |
17504 KB |
ok, correct split |
3 |
Correct |
10 ms |
17484 KB |
ok, correct split |
4 |
Correct |
10 ms |
17468 KB |
ok, correct split |
5 |
Correct |
10 ms |
17484 KB |
ok, correct split |
6 |
Correct |
10 ms |
17472 KB |
ok, correct split |
7 |
Correct |
162 ms |
37116 KB |
ok, correct split |
8 |
Correct |
134 ms |
35296 KB |
ok, correct split |
9 |
Correct |
144 ms |
34668 KB |
ok, correct split |
10 |
Correct |
215 ms |
37116 KB |
ok, correct split |
11 |
Correct |
158 ms |
36196 KB |
ok, correct split |
12 |
Correct |
9 ms |
17484 KB |
ok, correct split |
13 |
Correct |
10 ms |
17484 KB |
ok, correct split |
14 |
Correct |
9 ms |
17484 KB |
ok, correct split |
15 |
Correct |
177 ms |
33900 KB |
ok, correct split |
16 |
Correct |
175 ms |
32056 KB |
ok, correct split |
17 |
Correct |
143 ms |
37104 KB |
ok, correct split |
18 |
Correct |
150 ms |
35140 KB |
ok, correct split |
19 |
Correct |
205 ms |
35640 KB |
ok, correct split |
20 |
Correct |
142 ms |
31216 KB |
ok, correct split |
21 |
Correct |
85 ms |
28384 KB |
ok, correct split |
22 |
Correct |
84 ms |
28464 KB |
ok, correct split |
23 |
Correct |
77 ms |
28768 KB |
ok, correct split |
24 |
Correct |
10 ms |
17484 KB |
ok, correct split |
25 |
Correct |
202 ms |
31096 KB |
ok, correct split |
26 |
Correct |
46 ms |
23044 KB |
ok, correct split |
27 |
Correct |
9 ms |
17484 KB |
ok, correct split |
28 |
Correct |
146 ms |
32224 KB |
ok, correct split |
29 |
Correct |
194 ms |
32060 KB |
ok, correct split |
30 |
Correct |
146 ms |
31800 KB |
ok, correct split |
31 |
Correct |
143 ms |
32880 KB |
ok, correct split |
32 |
Correct |
146 ms |
31712 KB |
ok, correct split |
33 |
Correct |
60 ms |
22124 KB |
ok, no valid answer |
34 |
Correct |
60 ms |
24252 KB |
ok, no valid answer |
35 |
Correct |
106 ms |
29092 KB |
ok, no valid answer |
36 |
Correct |
139 ms |
30776 KB |
ok, no valid answer |
37 |
Correct |
110 ms |
27792 KB |
ok, no valid answer |
38 |
Correct |
12 ms |
17536 KB |
ok, correct split |
39 |
Correct |
10 ms |
17484 KB |
ok, no valid answer |
40 |
Correct |
10 ms |
17512 KB |
ok, correct split |
41 |
Correct |
10 ms |
17536 KB |
ok, correct split |
42 |
Correct |
10 ms |
17484 KB |
ok, correct split |
43 |
Correct |
10 ms |
17528 KB |
ok, correct split |
44 |
Correct |
10 ms |
17484 KB |
ok, correct split |
45 |
Correct |
10 ms |
17440 KB |
ok, correct split |
46 |
Correct |
14 ms |
17936 KB |
ok, correct split |
47 |
Correct |
12 ms |
17848 KB |
ok, correct split |
48 |
Correct |
10 ms |
17540 KB |
ok, correct split |
49 |
Correct |
13 ms |
17932 KB |
ok, correct split |
50 |
Correct |
10 ms |
17484 KB |
ok, correct split |
51 |
Correct |
10 ms |
17484 KB |
ok, correct split |
52 |
Correct |
10 ms |
17532 KB |
ok, correct split |
53 |
Correct |
10 ms |
17532 KB |
ok, correct split |
54 |
Correct |
10 ms |
17484 KB |
ok, correct split |
55 |
Correct |
9 ms |
17540 KB |
ok, correct split |
56 |
Correct |
10 ms |
17552 KB |
ok, correct split |
57 |
Correct |
11 ms |
17688 KB |
ok, correct split |
58 |
Correct |
12 ms |
17836 KB |
ok, correct split |
59 |
Correct |
12 ms |
17844 KB |
ok, correct split |
60 |
Correct |
15 ms |
17868 KB |
ok, correct split |
61 |
Correct |
15 ms |
17800 KB |
ok, correct split |
62 |
Correct |
11 ms |
17784 KB |
ok, correct split |
63 |
Correct |
12 ms |
17868 KB |
ok, correct split |
64 |
Correct |
12 ms |
17936 KB |
ok, correct split |
65 |
Correct |
13 ms |
17856 KB |
ok, correct split |
66 |
Correct |
11 ms |
17548 KB |
ok, correct split |
67 |
Correct |
12 ms |
17916 KB |
ok, correct split |
68 |
Correct |
11 ms |
17612 KB |
ok, correct split |
69 |
Correct |
11 ms |
17532 KB |
ok, correct split |
70 |
Correct |
10 ms |
17548 KB |
ok, correct split |
71 |
Correct |
11 ms |
17840 KB |
ok, correct split |
72 |
Correct |
12 ms |
17860 KB |
ok, correct split |
73 |
Correct |
11 ms |
17812 KB |
ok, correct split |
74 |
Correct |
15 ms |
17864 KB |
ok, correct split |
75 |
Correct |
13 ms |
17996 KB |
ok, correct split |
76 |
Correct |
16 ms |
17996 KB |
ok, correct split |
77 |
Correct |
13 ms |
17936 KB |
ok, correct split |
78 |
Correct |
11 ms |
17740 KB |
ok, correct split |
79 |
Correct |
11 ms |
17640 KB |
ok, correct split |
80 |
Correct |
13 ms |
17868 KB |
ok, correct split |
81 |
Correct |
12 ms |
17860 KB |
ok, correct split |
82 |
Correct |
12 ms |
17932 KB |
ok, correct split |
83 |
Correct |
11 ms |
17868 KB |
ok, correct split |
84 |
Correct |
12 ms |
17820 KB |
ok, no valid answer |
85 |
Correct |
14 ms |
17800 KB |
ok, correct split |
86 |
Correct |
11 ms |
17820 KB |
ok, correct split |
87 |
Correct |
9 ms |
17484 KB |
ok, no valid answer |
88 |
Correct |
9 ms |
17528 KB |
ok, no valid answer |
89 |
Correct |
11 ms |
17800 KB |
ok, no valid answer |
90 |
Correct |
12 ms |
17928 KB |
ok, no valid answer |
91 |
Correct |
11 ms |
17740 KB |
ok, no valid answer |
92 |
Correct |
11 ms |
17860 KB |
ok, no valid answer |
93 |
Correct |
15 ms |
17920 KB |
ok, no valid answer |
94 |
Correct |
191 ms |
33380 KB |
ok, correct split |
95 |
Correct |
194 ms |
36980 KB |
ok, correct split |
96 |
Correct |
180 ms |
35612 KB |
ok, correct split |
97 |
Correct |
48 ms |
23284 KB |
ok, correct split |
98 |
Correct |
50 ms |
23480 KB |
ok, correct split |
99 |
Correct |
59 ms |
25072 KB |
ok, correct split |
100 |
Correct |
207 ms |
35968 KB |
ok, correct split |
101 |
Correct |
182 ms |
34824 KB |
ok, correct split |
102 |
Correct |
154 ms |
33336 KB |
ok, correct split |
103 |
Correct |
154 ms |
33344 KB |
ok, correct split |
104 |
Correct |
148 ms |
37216 KB |
ok, correct split |
105 |
Correct |
91 ms |
26464 KB |
ok, correct split |
106 |
Correct |
154 ms |
34940 KB |
ok, correct split |
107 |
Correct |
135 ms |
32132 KB |
ok, correct split |
108 |
Correct |
137 ms |
32112 KB |
ok, correct split |
109 |
Correct |
179 ms |
35600 KB |
ok, correct split |
110 |
Correct |
192 ms |
35312 KB |
ok, correct split |
111 |
Correct |
208 ms |
35256 KB |
ok, correct split |
112 |
Correct |
175 ms |
35584 KB |
ok, correct split |
113 |
Correct |
200 ms |
35720 KB |
ok, correct split |
114 |
Correct |
23 ms |
19476 KB |
ok, correct split |
115 |
Correct |
20 ms |
19268 KB |
ok, correct split |
116 |
Correct |
161 ms |
34672 KB |
ok, correct split |
117 |
Correct |
164 ms |
34500 KB |
ok, correct split |
118 |
Correct |
145 ms |
31288 KB |
ok, correct split |
119 |
Correct |
173 ms |
31240 KB |
ok, correct split |
120 |
Correct |
172 ms |
33592 KB |
ok, correct split |
121 |
Correct |
144 ms |
32120 KB |
ok, no valid answer |
122 |
Correct |
148 ms |
31448 KB |
ok, no valid answer |
123 |
Correct |
245 ms |
37748 KB |
ok, no valid answer |
124 |
Correct |
209 ms |
37624 KB |
ok, no valid answer |
125 |
Correct |
117 ms |
31296 KB |
ok, no valid answer |
126 |
Correct |
84 ms |
27832 KB |
ok, no valid answer |
127 |
Correct |
137 ms |
33516 KB |
ok, no valid answer |