#include "split.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<int> edge[100005];
vector<int> treeEdge[100005];
bool visited[100005];
int cent;
int val[100005];
int csize[100005];
int treeNum[100005];
int parent[100005];
int treeSize[100005];
int compSize[100005];
bool usingTree[100005];
int usingSize;
void span(int root)
{
visited[root] = true;
for (auto& e : edge[root])
{
if (visited[e])
continue;
treeEdge[root].push_back(e);
treeEdge[e].push_back(root);
span(e);
}
}
int findCent(int root, int n)
{
csize[root] = 1;
bool isCent = true;
for (auto& e : treeEdge[root])
{
if (e == parent[root])
continue;
parent[e] = root;
int c = findCent(e, n);
if (c != -1)
return c;
csize[root] += csize[e];
isCent = isCent && (csize[e] <= n / 2);
}
if (isCent && n - csize[root] <= n / 2)
return root;
return -1;
}
void numbering(int root, int k)
{
treeNum[root] = k;
for (auto& e : treeEdge[root])
{
if (treeNum[e] != 0 || e == cent)
continue;
numbering(e, k);
}
}
int comp(int root)
{
int res = 0;
if (!usingTree[treeNum[root]])
{
res += treeSize[treeNum[root]];
usingTree[treeNum[root]] = true;
}
visited[root] = true;
for (auto& e : edge[root])
{
if (visited[e] || e == cent)
continue;
res += comp(e);
}
return res;
}
void findTree(int root, int sz)
{
if (usingSize >= sz)
return;
if (!usingTree[treeNum[root]])
{
usingSize += treeSize[treeNum[root]];
usingTree[treeNum[root]] = true;
}
visited[root] = true;
for (auto& e : edge[root])
{
if (visited[e] || e == cent)
continue;
findTree(e, sz);
}
}
void mark(int root, int v, int& sz)
{
if (sz == 0)
return;
val[root] = v;
sz--;
for (auto& e : edge[root])
{
if (val[e] != 0 || !usingTree[treeNum[e]])
continue;
mark(e, v, sz);
}
}
void mark2(int root, int v, int& sz)
{
if (sz == 0)
return;
val[root] = v;
sz--;
for (auto& e : edge[root])
{
if (val[e] != 0)
continue;
mark2(e, v, sz);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
vector<ii> v = { { a, 1 }, { b, 2 }, { c, 3 } };
for (int i = 0; i < p.size(); i++)
{
edge[p[i]].push_back(q[i]);
edge[q[i]].push_back(p[i]);
}
span(0);
sort(all(v));
cent = findCent(0, n);
// centroid 제외한 그래프에서 a이상의 크기인 트리가 있는지 확인, 있으면 go
int tr = 1;
for (auto& e : treeEdge[cent])
{
numbering(e, tr);
tr++;
}
for (int i = 0; i < n; i++)
treeSize[treeNum[i]]++;
for (int k = 1; k < tr; k++)
{
if (treeSize[k] < v[0].xx)
continue;
int e = -1;
for (auto& ei : treeEdge[cent])
{
if (treeNum[ei] == k)
e = ei;
}
assert(e != -1);
//이 경우, 얘 하나만 써도 OK
usingTree[k] = true;
mark(e, v[0].yy, v[0].xx);
mark2(cent, v[1].yy, v[1].xx);
for (int j = 0; j < n; j++)
if (val[j] == 0)
val[j] = v[2].yy;
vector<int> result(n);
for (int j = 0; j < n; j++)
result[j] = val[j];
return result;
}
memset(visited, false, sizeof(visited));
for (auto& e : treeEdge[cent])
{
int c = comp(e);
if (c < v[0].xx)
continue;
// 합해서 a이상 되는 트리 확인 후, 그 트리에 속하는 원소들만 이용해서 a개수 만든다
memset(visited, false, sizeof(visited));
memset(usingTree, false, sizeof(usingTree));
findTree(e, v[0].xx);
mark(e, v[0].yy, v[0].xx);
mark2(cent, v[1].yy, v[1].xx);
for (int i = 0; i < n; i++)
if (val[i] == 0)
val[i] = v[2].yy;
break;
}
vector<int> result(n);
for (int i = 0; i < n; i++)
result[i] = val[i];
return result;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:178:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < p.size(); i++)
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
ok, correct split |
2 |
Correct |
6 ms |
5112 KB |
ok, correct split |
3 |
Correct |
6 ms |
5112 KB |
ok, correct split |
4 |
Correct |
6 ms |
4988 KB |
ok, correct split |
5 |
Correct |
6 ms |
5112 KB |
ok, correct split |
6 |
Correct |
6 ms |
4856 KB |
ok, correct split |
7 |
Correct |
160 ms |
22388 KB |
ok, correct split |
8 |
Correct |
133 ms |
20088 KB |
ok, correct split |
9 |
Correct |
165 ms |
19460 KB |
ok, correct split |
10 |
Correct |
148 ms |
22776 KB |
ok, correct split |
11 |
Correct |
164 ms |
22740 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
6 ms |
4984 KB |
ok, correct split |
3 |
Correct |
6 ms |
5112 KB |
ok, correct split |
4 |
Correct |
173 ms |
19576 KB |
ok, correct split |
5 |
Correct |
141 ms |
15184 KB |
ok, correct split |
6 |
Correct |
155 ms |
22868 KB |
ok, correct split |
7 |
Correct |
149 ms |
19964 KB |
ok, correct split |
8 |
Correct |
177 ms |
17016 KB |
ok, correct split |
9 |
Correct |
142 ms |
14968 KB |
ok, correct split |
10 |
Correct |
99 ms |
16112 KB |
ok, correct split |
11 |
Correct |
101 ms |
16112 KB |
ok, correct split |
12 |
Correct |
102 ms |
16120 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
ok, correct split |
2 |
Correct |
137 ms |
15096 KB |
ok, correct split |
3 |
Correct |
47 ms |
9080 KB |
ok, correct split |
4 |
Correct |
10 ms |
5116 KB |
ok, correct split |
5 |
Correct |
163 ms |
17528 KB |
ok, correct split |
6 |
Correct |
175 ms |
17224 KB |
ok, correct split |
7 |
Correct |
162 ms |
17016 KB |
ok, correct split |
8 |
Correct |
163 ms |
18424 KB |
ok, correct split |
9 |
Correct |
148 ms |
16908 KB |
ok, correct split |
10 |
Correct |
39 ms |
8440 KB |
ok, no valid answer |
11 |
Correct |
62 ms |
9976 KB |
ok, no valid answer |
12 |
Correct |
120 ms |
15348 KB |
ok, no valid answer |
13 |
Correct |
138 ms |
14812 KB |
ok, no valid answer |
14 |
Correct |
103 ms |
15768 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
ok, correct split |
2 |
Correct |
6 ms |
5112 KB |
ok, no valid answer |
3 |
Correct |
6 ms |
5084 KB |
ok, correct split |
4 |
Correct |
6 ms |
4984 KB |
ok, correct split |
5 |
Correct |
6 ms |
4984 KB |
ok, correct split |
6 |
Correct |
6 ms |
5012 KB |
ok, correct split |
7 |
Correct |
6 ms |
4984 KB |
ok, correct split |
8 |
Correct |
7 ms |
5112 KB |
ok, correct split |
9 |
Correct |
9 ms |
5372 KB |
ok, correct split |
10 |
Correct |
9 ms |
5368 KB |
ok, correct split |
11 |
Correct |
6 ms |
5112 KB |
ok, correct split |
12 |
Correct |
9 ms |
5368 KB |
ok, correct split |
13 |
Correct |
6 ms |
4984 KB |
ok, correct split |
14 |
Correct |
6 ms |
4984 KB |
ok, correct split |
15 |
Correct |
7 ms |
4984 KB |
ok, correct split |
16 |
Correct |
7 ms |
5112 KB |
ok, correct split |
17 |
Correct |
8 ms |
5112 KB |
ok, correct split |
18 |
Correct |
6 ms |
5112 KB |
ok, correct split |
19 |
Correct |
7 ms |
5112 KB |
ok, correct split |
20 |
Correct |
8 ms |
5240 KB |
ok, correct split |
21 |
Correct |
9 ms |
5368 KB |
ok, correct split |
22 |
Correct |
10 ms |
5368 KB |
ok, correct split |
23 |
Correct |
10 ms |
5368 KB |
ok, correct split |
24 |
Correct |
10 ms |
5368 KB |
ok, correct split |
25 |
Correct |
10 ms |
5368 KB |
ok, correct split |
26 |
Correct |
11 ms |
5624 KB |
ok, correct split |
27 |
Correct |
9 ms |
5624 KB |
ok, correct split |
28 |
Correct |
9 ms |
5624 KB |
ok, correct split |
29 |
Correct |
7 ms |
5240 KB |
ok, correct split |
30 |
Correct |
11 ms |
5368 KB |
ok, correct split |
31 |
Correct |
7 ms |
5112 KB |
ok, correct split |
32 |
Correct |
8 ms |
5112 KB |
ok, correct split |
33 |
Correct |
8 ms |
5112 KB |
ok, correct split |
34 |
Correct |
9 ms |
5496 KB |
ok, correct split |
35 |
Correct |
9 ms |
5496 KB |
ok, correct split |
36 |
Correct |
10 ms |
5496 KB |
ok, correct split |
37 |
Correct |
7 ms |
5496 KB |
ok, correct split |
38 |
Correct |
10 ms |
5624 KB |
ok, correct split |
39 |
Correct |
12 ms |
5624 KB |
ok, correct split |
40 |
Correct |
9 ms |
5368 KB |
ok, correct split |
41 |
Correct |
8 ms |
5240 KB |
ok, correct split |
42 |
Correct |
7 ms |
5240 KB |
ok, correct split |
43 |
Correct |
10 ms |
5628 KB |
ok, correct split |
44 |
Correct |
9 ms |
5368 KB |
ok, correct split |
45 |
Correct |
12 ms |
5628 KB |
ok, correct split |
46 |
Correct |
10 ms |
5368 KB |
ok, correct split |
47 |
Correct |
9 ms |
5500 KB |
ok, no valid answer |
48 |
Correct |
10 ms |
5368 KB |
ok, correct split |
49 |
Correct |
10 ms |
5496 KB |
ok, correct split |
50 |
Correct |
8 ms |
5112 KB |
ok, no valid answer |
51 |
Correct |
8 ms |
5240 KB |
ok, no valid answer |
52 |
Correct |
10 ms |
5372 KB |
ok, no valid answer |
53 |
Correct |
12 ms |
5496 KB |
ok, no valid answer |
54 |
Correct |
8 ms |
5368 KB |
ok, no valid answer |
55 |
Correct |
9 ms |
5496 KB |
ok, no valid answer |
56 |
Correct |
8 ms |
5496 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
ok, correct split |
2 |
Correct |
6 ms |
5112 KB |
ok, correct split |
3 |
Correct |
6 ms |
5112 KB |
ok, correct split |
4 |
Correct |
6 ms |
4988 KB |
ok, correct split |
5 |
Correct |
6 ms |
5112 KB |
ok, correct split |
6 |
Correct |
6 ms |
4856 KB |
ok, correct split |
7 |
Correct |
160 ms |
22388 KB |
ok, correct split |
8 |
Correct |
133 ms |
20088 KB |
ok, correct split |
9 |
Correct |
165 ms |
19460 KB |
ok, correct split |
10 |
Correct |
148 ms |
22776 KB |
ok, correct split |
11 |
Correct |
164 ms |
22740 KB |
ok, correct split |
12 |
Correct |
6 ms |
4984 KB |
ok, correct split |
13 |
Correct |
6 ms |
4984 KB |
ok, correct split |
14 |
Correct |
6 ms |
5112 KB |
ok, correct split |
15 |
Correct |
173 ms |
19576 KB |
ok, correct split |
16 |
Correct |
141 ms |
15184 KB |
ok, correct split |
17 |
Correct |
155 ms |
22868 KB |
ok, correct split |
18 |
Correct |
149 ms |
19964 KB |
ok, correct split |
19 |
Correct |
177 ms |
17016 KB |
ok, correct split |
20 |
Correct |
142 ms |
14968 KB |
ok, correct split |
21 |
Correct |
99 ms |
16112 KB |
ok, correct split |
22 |
Correct |
101 ms |
16112 KB |
ok, correct split |
23 |
Correct |
102 ms |
16120 KB |
ok, correct split |
24 |
Correct |
6 ms |
4984 KB |
ok, correct split |
25 |
Correct |
137 ms |
15096 KB |
ok, correct split |
26 |
Correct |
47 ms |
9080 KB |
ok, correct split |
27 |
Correct |
10 ms |
5116 KB |
ok, correct split |
28 |
Correct |
163 ms |
17528 KB |
ok, correct split |
29 |
Correct |
175 ms |
17224 KB |
ok, correct split |
30 |
Correct |
162 ms |
17016 KB |
ok, correct split |
31 |
Correct |
163 ms |
18424 KB |
ok, correct split |
32 |
Correct |
148 ms |
16908 KB |
ok, correct split |
33 |
Correct |
39 ms |
8440 KB |
ok, no valid answer |
34 |
Correct |
62 ms |
9976 KB |
ok, no valid answer |
35 |
Correct |
120 ms |
15348 KB |
ok, no valid answer |
36 |
Correct |
138 ms |
14812 KB |
ok, no valid answer |
37 |
Correct |
103 ms |
15768 KB |
ok, no valid answer |
38 |
Correct |
6 ms |
5112 KB |
ok, correct split |
39 |
Correct |
6 ms |
5112 KB |
ok, no valid answer |
40 |
Correct |
6 ms |
5084 KB |
ok, correct split |
41 |
Correct |
6 ms |
4984 KB |
ok, correct split |
42 |
Correct |
6 ms |
4984 KB |
ok, correct split |
43 |
Correct |
6 ms |
5012 KB |
ok, correct split |
44 |
Correct |
6 ms |
4984 KB |
ok, correct split |
45 |
Correct |
7 ms |
5112 KB |
ok, correct split |
46 |
Correct |
9 ms |
5372 KB |
ok, correct split |
47 |
Correct |
9 ms |
5368 KB |
ok, correct split |
48 |
Correct |
6 ms |
5112 KB |
ok, correct split |
49 |
Correct |
9 ms |
5368 KB |
ok, correct split |
50 |
Correct |
6 ms |
4984 KB |
ok, correct split |
51 |
Correct |
6 ms |
4984 KB |
ok, correct split |
52 |
Correct |
7 ms |
4984 KB |
ok, correct split |
53 |
Correct |
7 ms |
5112 KB |
ok, correct split |
54 |
Correct |
8 ms |
5112 KB |
ok, correct split |
55 |
Correct |
6 ms |
5112 KB |
ok, correct split |
56 |
Correct |
7 ms |
5112 KB |
ok, correct split |
57 |
Correct |
8 ms |
5240 KB |
ok, correct split |
58 |
Correct |
9 ms |
5368 KB |
ok, correct split |
59 |
Correct |
10 ms |
5368 KB |
ok, correct split |
60 |
Correct |
10 ms |
5368 KB |
ok, correct split |
61 |
Correct |
10 ms |
5368 KB |
ok, correct split |
62 |
Correct |
10 ms |
5368 KB |
ok, correct split |
63 |
Correct |
11 ms |
5624 KB |
ok, correct split |
64 |
Correct |
9 ms |
5624 KB |
ok, correct split |
65 |
Correct |
9 ms |
5624 KB |
ok, correct split |
66 |
Correct |
7 ms |
5240 KB |
ok, correct split |
67 |
Correct |
11 ms |
5368 KB |
ok, correct split |
68 |
Correct |
7 ms |
5112 KB |
ok, correct split |
69 |
Correct |
8 ms |
5112 KB |
ok, correct split |
70 |
Correct |
8 ms |
5112 KB |
ok, correct split |
71 |
Correct |
9 ms |
5496 KB |
ok, correct split |
72 |
Correct |
9 ms |
5496 KB |
ok, correct split |
73 |
Correct |
10 ms |
5496 KB |
ok, correct split |
74 |
Correct |
7 ms |
5496 KB |
ok, correct split |
75 |
Correct |
10 ms |
5624 KB |
ok, correct split |
76 |
Correct |
12 ms |
5624 KB |
ok, correct split |
77 |
Correct |
9 ms |
5368 KB |
ok, correct split |
78 |
Correct |
8 ms |
5240 KB |
ok, correct split |
79 |
Correct |
7 ms |
5240 KB |
ok, correct split |
80 |
Correct |
10 ms |
5628 KB |
ok, correct split |
81 |
Correct |
9 ms |
5368 KB |
ok, correct split |
82 |
Correct |
12 ms |
5628 KB |
ok, correct split |
83 |
Correct |
10 ms |
5368 KB |
ok, correct split |
84 |
Correct |
9 ms |
5500 KB |
ok, no valid answer |
85 |
Correct |
10 ms |
5368 KB |
ok, correct split |
86 |
Correct |
10 ms |
5496 KB |
ok, correct split |
87 |
Correct |
8 ms |
5112 KB |
ok, no valid answer |
88 |
Correct |
8 ms |
5240 KB |
ok, no valid answer |
89 |
Correct |
10 ms |
5372 KB |
ok, no valid answer |
90 |
Correct |
12 ms |
5496 KB |
ok, no valid answer |
91 |
Correct |
8 ms |
5368 KB |
ok, no valid answer |
92 |
Correct |
9 ms |
5496 KB |
ok, no valid answer |
93 |
Correct |
8 ms |
5496 KB |
ok, no valid answer |
94 |
Correct |
154 ms |
19064 KB |
ok, correct split |
95 |
Correct |
229 ms |
24300 KB |
ok, correct split |
96 |
Correct |
217 ms |
22592 KB |
ok, correct split |
97 |
Correct |
63 ms |
9592 KB |
ok, correct split |
98 |
Correct |
51 ms |
9720 KB |
ok, correct split |
99 |
Correct |
70 ms |
11768 KB |
ok, correct split |
100 |
Correct |
211 ms |
19804 KB |
ok, correct split |
101 |
Correct |
179 ms |
18680 KB |
ok, correct split |
102 |
Correct |
160 ms |
18544 KB |
ok, correct split |
103 |
Correct |
155 ms |
18416 KB |
ok, correct split |
104 |
Correct |
148 ms |
20068 KB |
ok, correct split |
105 |
Correct |
90 ms |
12152 KB |
ok, correct split |
106 |
Correct |
157 ms |
20460 KB |
ok, correct split |
107 |
Correct |
147 ms |
16376 KB |
ok, correct split |
108 |
Correct |
154 ms |
16376 KB |
ok, correct split |
109 |
Correct |
220 ms |
19256 KB |
ok, correct split |
110 |
Correct |
214 ms |
19392 KB |
ok, correct split |
111 |
Correct |
229 ms |
19448 KB |
ok, correct split |
112 |
Correct |
206 ms |
19572 KB |
ok, correct split |
113 |
Correct |
198 ms |
19696 KB |
ok, correct split |
114 |
Correct |
25 ms |
6904 KB |
ok, correct split |
115 |
Correct |
20 ms |
6648 KB |
ok, correct split |
116 |
Correct |
272 ms |
19288 KB |
ok, correct split |
117 |
Correct |
197 ms |
19196 KB |
ok, correct split |
118 |
Correct |
145 ms |
16248 KB |
ok, correct split |
119 |
Correct |
145 ms |
16192 KB |
ok, correct split |
120 |
Correct |
157 ms |
20204 KB |
ok, correct split |
121 |
Correct |
131 ms |
15864 KB |
ok, no valid answer |
122 |
Correct |
151 ms |
16108 KB |
ok, no valid answer |
123 |
Correct |
201 ms |
19576 KB |
ok, no valid answer |
124 |
Correct |
200 ms |
19652 KB |
ok, no valid answer |
125 |
Correct |
127 ms |
17648 KB |
ok, no valid answer |
126 |
Correct |
89 ms |
15728 KB |
ok, no valid answer |
127 |
Correct |
156 ms |
17888 KB |
ok, no valid answer |