#include <bits/stdc++.h>
#include "split.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
const ll NMAX = 100001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;
vector <int> sol;
vector <int> v[NMAX], tree[NMAX], nou[NMAX];
int lvl[NMAX];
int sz[NMAX];
void DFS(int node) {
for(auto x : v[node]) {
if(lvl[x])
continue;
tree[node].push_back(x);
tree[x].push_back(node);
lvl[x] = lvl[node] + 1;
DFS(x);
}
}
int total = 0;
void getsz(int node, int p) {
sz[node] = 1;
for(auto x : tree[node]) {
if(x == p)
continue;
getsz(x, node);
sz[node] += sz[x];
}
total = sz[node];
}
int root;
vector <int> sons[NMAX];
int cc;
int cnt[NMAX];
int findCentroid(int node, int p) {
for(auto x : tree[node]) {
if(x == p)
continue;
if(sz[x] > total / 2)
return findCentroid(x, node);
}
return node;
}
int comp[NMAX];
void baga(int node, int p) {
comp[node] = cc;
cnt[cc]++;
for(auto x : tree[node]) {
if(x == p)
continue;
baga(x, node);
}
}
int col[4];
int cate;
void marcheaza(int node, int p, int cul) {
if(cate == 0)
return;
sol[node] = cul;
cate--;
for(auto x : tree[node]) {
if(x == p || sol[x] != 0)
continue;
marcheaza(x, node, cul);
}
}
int viz[NMAX];
vector <int> cine;
void greedy(int node) {
viz[node] = 1;
if(cate <= 0)
return;
cate -= cnt[node];
cine.push_back(node);
for(auto x : nou[node]) {
if(viz[x])
continue;
greedy(x);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
col[0] = 1;
col[1] = 2;
col[2] = 3;
sol.resize(n);
if(a > b) {
swap(a, b);
swap(col[0], col[1]);
}
if(b > c) {
swap(c, b);
swap(col[2], col[1]);
}
if(a > b) {
swap(a, b);
swap(col[0], col[1]);
}
for(int i = 0; i < p.size(); i++) {
int a = p[i];
int b = q[i];
v[a].push_back(b);
v[b].push_back(a);
}
lvl[0] = 1;
DFS(0);
getsz(0, -1);
root = findCentroid(0, -1);
for(auto x : tree[root]) {
cc = x; /// Componenta poarta numele celui mai inalt din ea (reprezentantul e fiu a root-ului)
baga(x, root);
}
getsz(root, -1);
int maxim = -1;
for(auto x : tree[root]) {
if(maxim == -1 || sz[maxim] < sz[x])
maxim = x;
}
if(sz[maxim] >= a) {
cate = a;
marcheaza(maxim, root, col[0]);
cate = b;
marcheaza(root, -1, col[1]);
for(int i = 0; i < n; i++) {
if(sol[i] == 0)
sol[i] = col[2];
}
return sol;
}
int cnv = -1;
for(int i = 0; i < n; i++) {
if(i == root)
continue;
for(auto x : v[i]) {
if(x == root)
continue;
if(abs(lvl[i] - lvl[x]) == 1)
continue;
nou[comp[i]].push_back(comp[x]);
}
}
cate = a;
viz[root] = 1;
for(int i = 0; i < n; i++){
cate = a;
if(!viz[comp[i]]){
greedy(comp[i]);
if(cate <= 0)
break;
}
cine.clear();
}
cate = a;
for(auto x : cine) {
marcheaza(x, root, col[0]);
}
if(cate > 0){
for(int i = 0; i < n; i++){
sol[i] = 0;
}
return sol;
}
cate = b;
marcheaza(root, -1, col[1]);
for(int i = 0; i < n; i++) {
if(sol[i] == 0)
sol[i] = col[2];
}
return sol;
}
Compilation message
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i = 0; i < p.size(); i++) {
| ~~^~~~~~~~~~
split.cpp:157:9: warning: unused variable 'cnv' [-Wunused-variable]
157 | int cnv = -1;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, correct split |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
5 ms |
9684 KB |
ok, correct split |
6 |
Correct |
5 ms |
9684 KB |
ok, correct split |
7 |
Correct |
102 ms |
26828 KB |
ok, correct split |
8 |
Correct |
112 ms |
24652 KB |
ok, correct split |
9 |
Correct |
96 ms |
24016 KB |
ok, correct split |
10 |
Correct |
109 ms |
27188 KB |
ok, correct split |
11 |
Correct |
105 ms |
27284 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
9624 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, correct split |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
124 ms |
24064 KB |
ok, correct split |
5 |
Correct |
92 ms |
19692 KB |
ok, correct split |
6 |
Correct |
94 ms |
27212 KB |
ok, correct split |
7 |
Correct |
112 ms |
24436 KB |
ok, correct split |
8 |
Correct |
128 ms |
21824 KB |
ok, correct split |
9 |
Correct |
88 ms |
19548 KB |
ok, correct split |
10 |
Correct |
63 ms |
20564 KB |
ok, correct split |
11 |
Correct |
64 ms |
20636 KB |
ok, correct split |
12 |
Correct |
64 ms |
20636 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
ok, correct split |
2 |
Correct |
97 ms |
19664 KB |
ok, correct split |
3 |
Correct |
32 ms |
13880 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
92 ms |
22076 KB |
ok, correct split |
6 |
Correct |
94 ms |
21736 KB |
ok, correct split |
7 |
Correct |
109 ms |
21756 KB |
ok, correct split |
8 |
Correct |
95 ms |
22908 KB |
ok, correct split |
9 |
Correct |
95 ms |
21936 KB |
ok, correct split |
10 |
Correct |
31 ms |
13268 KB |
ok, no valid answer |
11 |
Correct |
40 ms |
15028 KB |
ok, no valid answer |
12 |
Correct |
74 ms |
20728 KB |
ok, no valid answer |
13 |
Correct |
94 ms |
20528 KB |
ok, no valid answer |
14 |
Correct |
65 ms |
21032 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
7 ms |
9684 KB |
ok, correct split |
6 |
Correct |
5 ms |
9684 KB |
ok, correct split |
7 |
Correct |
7 ms |
9612 KB |
ok, correct split |
8 |
Correct |
5 ms |
9684 KB |
ok, correct split |
9 |
Correct |
7 ms |
10028 KB |
ok, correct split |
10 |
Correct |
7 ms |
9992 KB |
ok, correct split |
11 |
Correct |
5 ms |
9684 KB |
ok, correct split |
12 |
Correct |
7 ms |
9996 KB |
ok, correct split |
13 |
Correct |
5 ms |
9688 KB |
ok, correct split |
14 |
Correct |
5 ms |
9684 KB |
ok, correct split |
15 |
Correct |
5 ms |
9684 KB |
ok, correct split |
16 |
Correct |
5 ms |
9684 KB |
ok, correct split |
17 |
Correct |
5 ms |
9684 KB |
ok, correct split |
18 |
Correct |
5 ms |
9684 KB |
ok, correct split |
19 |
Correct |
6 ms |
9756 KB |
ok, correct split |
20 |
Correct |
7 ms |
9812 KB |
ok, correct split |
21 |
Correct |
8 ms |
9940 KB |
ok, correct split |
22 |
Correct |
7 ms |
9940 KB |
ok, correct split |
23 |
Correct |
6 ms |
9940 KB |
ok, correct split |
24 |
Correct |
6 ms |
9940 KB |
ok, correct split |
25 |
Correct |
7 ms |
9940 KB |
ok, correct split |
26 |
Correct |
7 ms |
10068 KB |
ok, correct split |
27 |
Correct |
7 ms |
10068 KB |
ok, correct split |
28 |
Correct |
7 ms |
10068 KB |
ok, correct split |
29 |
Correct |
8 ms |
9684 KB |
ok, correct split |
30 |
Correct |
7 ms |
10036 KB |
ok, correct split |
31 |
Correct |
5 ms |
9684 KB |
ok, correct split |
32 |
Correct |
5 ms |
9704 KB |
ok, correct split |
33 |
Correct |
5 ms |
9684 KB |
ok, correct split |
34 |
Correct |
7 ms |
9940 KB |
ok, correct split |
35 |
Correct |
7 ms |
9940 KB |
ok, correct split |
36 |
Correct |
7 ms |
9940 KB |
ok, correct split |
37 |
Correct |
7 ms |
10068 KB |
ok, correct split |
38 |
Correct |
7 ms |
10068 KB |
ok, correct split |
39 |
Correct |
7 ms |
9968 KB |
ok, correct split |
40 |
Correct |
7 ms |
9940 KB |
ok, correct split |
41 |
Correct |
6 ms |
9812 KB |
ok, correct split |
42 |
Correct |
6 ms |
9812 KB |
ok, correct split |
43 |
Correct |
7 ms |
10068 KB |
ok, correct split |
44 |
Correct |
8 ms |
10004 KB |
ok, correct split |
45 |
Correct |
8 ms |
10068 KB |
ok, correct split |
46 |
Correct |
7 ms |
9988 KB |
ok, correct split |
47 |
Correct |
6 ms |
9992 KB |
ok, no valid answer |
48 |
Correct |
7 ms |
9940 KB |
ok, correct split |
49 |
Correct |
8 ms |
10068 KB |
ok, correct split |
50 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
51 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
52 |
Correct |
6 ms |
9940 KB |
ok, no valid answer |
53 |
Correct |
7 ms |
10068 KB |
ok, no valid answer |
54 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
55 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
56 |
Correct |
7 ms |
10012 KB |
ok, no valid answer |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
ok, correct split |
2 |
Correct |
5 ms |
9684 KB |
ok, correct split |
3 |
Correct |
5 ms |
9684 KB |
ok, correct split |
4 |
Correct |
5 ms |
9684 KB |
ok, correct split |
5 |
Correct |
5 ms |
9684 KB |
ok, correct split |
6 |
Correct |
5 ms |
9684 KB |
ok, correct split |
7 |
Correct |
102 ms |
26828 KB |
ok, correct split |
8 |
Correct |
112 ms |
24652 KB |
ok, correct split |
9 |
Correct |
96 ms |
24016 KB |
ok, correct split |
10 |
Correct |
109 ms |
27188 KB |
ok, correct split |
11 |
Correct |
105 ms |
27284 KB |
ok, correct split |
12 |
Correct |
4 ms |
9624 KB |
ok, correct split |
13 |
Correct |
5 ms |
9684 KB |
ok, correct split |
14 |
Correct |
5 ms |
9684 KB |
ok, correct split |
15 |
Correct |
124 ms |
24064 KB |
ok, correct split |
16 |
Correct |
92 ms |
19692 KB |
ok, correct split |
17 |
Correct |
94 ms |
27212 KB |
ok, correct split |
18 |
Correct |
112 ms |
24436 KB |
ok, correct split |
19 |
Correct |
128 ms |
21824 KB |
ok, correct split |
20 |
Correct |
88 ms |
19548 KB |
ok, correct split |
21 |
Correct |
63 ms |
20564 KB |
ok, correct split |
22 |
Correct |
64 ms |
20636 KB |
ok, correct split |
23 |
Correct |
64 ms |
20636 KB |
ok, correct split |
24 |
Correct |
5 ms |
9684 KB |
ok, correct split |
25 |
Correct |
97 ms |
19664 KB |
ok, correct split |
26 |
Correct |
32 ms |
13880 KB |
ok, correct split |
27 |
Correct |
5 ms |
9684 KB |
ok, correct split |
28 |
Correct |
92 ms |
22076 KB |
ok, correct split |
29 |
Correct |
94 ms |
21736 KB |
ok, correct split |
30 |
Correct |
109 ms |
21756 KB |
ok, correct split |
31 |
Correct |
95 ms |
22908 KB |
ok, correct split |
32 |
Correct |
95 ms |
21936 KB |
ok, correct split |
33 |
Correct |
31 ms |
13268 KB |
ok, no valid answer |
34 |
Correct |
40 ms |
15028 KB |
ok, no valid answer |
35 |
Correct |
74 ms |
20728 KB |
ok, no valid answer |
36 |
Correct |
94 ms |
20528 KB |
ok, no valid answer |
37 |
Correct |
65 ms |
21032 KB |
ok, no valid answer |
38 |
Correct |
5 ms |
9684 KB |
ok, correct split |
39 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
40 |
Correct |
5 ms |
9684 KB |
ok, correct split |
41 |
Correct |
5 ms |
9684 KB |
ok, correct split |
42 |
Correct |
7 ms |
9684 KB |
ok, correct split |
43 |
Correct |
5 ms |
9684 KB |
ok, correct split |
44 |
Correct |
7 ms |
9612 KB |
ok, correct split |
45 |
Correct |
5 ms |
9684 KB |
ok, correct split |
46 |
Correct |
7 ms |
10028 KB |
ok, correct split |
47 |
Correct |
7 ms |
9992 KB |
ok, correct split |
48 |
Correct |
5 ms |
9684 KB |
ok, correct split |
49 |
Correct |
7 ms |
9996 KB |
ok, correct split |
50 |
Correct |
5 ms |
9688 KB |
ok, correct split |
51 |
Correct |
5 ms |
9684 KB |
ok, correct split |
52 |
Correct |
5 ms |
9684 KB |
ok, correct split |
53 |
Correct |
5 ms |
9684 KB |
ok, correct split |
54 |
Correct |
5 ms |
9684 KB |
ok, correct split |
55 |
Correct |
5 ms |
9684 KB |
ok, correct split |
56 |
Correct |
6 ms |
9756 KB |
ok, correct split |
57 |
Correct |
7 ms |
9812 KB |
ok, correct split |
58 |
Correct |
8 ms |
9940 KB |
ok, correct split |
59 |
Correct |
7 ms |
9940 KB |
ok, correct split |
60 |
Correct |
6 ms |
9940 KB |
ok, correct split |
61 |
Correct |
6 ms |
9940 KB |
ok, correct split |
62 |
Correct |
7 ms |
9940 KB |
ok, correct split |
63 |
Correct |
7 ms |
10068 KB |
ok, correct split |
64 |
Correct |
7 ms |
10068 KB |
ok, correct split |
65 |
Correct |
7 ms |
10068 KB |
ok, correct split |
66 |
Correct |
8 ms |
9684 KB |
ok, correct split |
67 |
Correct |
7 ms |
10036 KB |
ok, correct split |
68 |
Correct |
5 ms |
9684 KB |
ok, correct split |
69 |
Correct |
5 ms |
9704 KB |
ok, correct split |
70 |
Correct |
5 ms |
9684 KB |
ok, correct split |
71 |
Correct |
7 ms |
9940 KB |
ok, correct split |
72 |
Correct |
7 ms |
9940 KB |
ok, correct split |
73 |
Correct |
7 ms |
9940 KB |
ok, correct split |
74 |
Correct |
7 ms |
10068 KB |
ok, correct split |
75 |
Correct |
7 ms |
10068 KB |
ok, correct split |
76 |
Correct |
7 ms |
9968 KB |
ok, correct split |
77 |
Correct |
7 ms |
9940 KB |
ok, correct split |
78 |
Correct |
6 ms |
9812 KB |
ok, correct split |
79 |
Correct |
6 ms |
9812 KB |
ok, correct split |
80 |
Correct |
7 ms |
10068 KB |
ok, correct split |
81 |
Correct |
8 ms |
10004 KB |
ok, correct split |
82 |
Correct |
8 ms |
10068 KB |
ok, correct split |
83 |
Correct |
7 ms |
9988 KB |
ok, correct split |
84 |
Correct |
6 ms |
9992 KB |
ok, no valid answer |
85 |
Correct |
7 ms |
9940 KB |
ok, correct split |
86 |
Correct |
8 ms |
10068 KB |
ok, correct split |
87 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
88 |
Correct |
5 ms |
9684 KB |
ok, no valid answer |
89 |
Correct |
6 ms |
9940 KB |
ok, no valid answer |
90 |
Correct |
7 ms |
10068 KB |
ok, no valid answer |
91 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
92 |
Correct |
7 ms |
9940 KB |
ok, no valid answer |
93 |
Correct |
7 ms |
10012 KB |
ok, no valid answer |
94 |
Correct |
99 ms |
22220 KB |
ok, correct split |
95 |
Correct |
142 ms |
26380 KB |
ok, correct split |
96 |
Correct |
129 ms |
24988 KB |
ok, correct split |
97 |
Correct |
31 ms |
13816 KB |
ok, correct split |
98 |
Correct |
33 ms |
13904 KB |
ok, correct split |
99 |
Correct |
49 ms |
15308 KB |
ok, correct split |
100 |
Correct |
118 ms |
22396 KB |
ok, correct split |
101 |
Correct |
108 ms |
21660 KB |
ok, correct split |
102 |
Correct |
106 ms |
21444 KB |
ok, correct split |
103 |
Correct |
97 ms |
21312 KB |
ok, correct split |
104 |
Correct |
103 ms |
22420 KB |
ok, correct split |
105 |
Correct |
53 ms |
16552 KB |
ok, correct split |
106 |
Correct |
106 ms |
26884 KB |
ok, correct split |
107 |
Correct |
83 ms |
20444 KB |
ok, correct split |
108 |
Correct |
86 ms |
20140 KB |
ok, correct split |
109 |
Correct |
122 ms |
23416 KB |
ok, correct split |
110 |
Correct |
121 ms |
23192 KB |
ok, correct split |
111 |
Correct |
118 ms |
22904 KB |
ok, correct split |
112 |
Correct |
120 ms |
23564 KB |
ok, correct split |
113 |
Correct |
116 ms |
23184 KB |
ok, correct split |
114 |
Correct |
16 ms |
11296 KB |
ok, correct split |
115 |
Correct |
15 ms |
10972 KB |
ok, correct split |
116 |
Correct |
118 ms |
23344 KB |
ok, correct split |
117 |
Correct |
114 ms |
22832 KB |
ok, correct split |
118 |
Correct |
88 ms |
19532 KB |
ok, correct split |
119 |
Correct |
95 ms |
19824 KB |
ok, correct split |
120 |
Correct |
92 ms |
23636 KB |
ok, correct split |
121 |
Correct |
85 ms |
20400 KB |
ok, no valid answer |
122 |
Correct |
81 ms |
20484 KB |
ok, no valid answer |
123 |
Correct |
131 ms |
23668 KB |
ok, no valid answer |
124 |
Correct |
129 ms |
24208 KB |
ok, no valid answer |
125 |
Correct |
82 ms |
21496 KB |
ok, no valid answer |
126 |
Correct |
57 ms |
19908 KB |
ok, no valid answer |
127 |
Correct |
93 ms |
21720 KB |
ok, no valid answer |