#include "split.h"
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
vector<pair<int , int> >gru;
vector<int> vis;
vector<int>gr[500000];
int re , pl = -1 , maxi = mod , f[500000] ,pl2 , menge;
int unt[300000] , ob[300000];
int dfs(int x){
int sub = 1;
vis[x] = 1;
for(int i = 0 ; i< gr[x].size() ; i ++){
int kind = gr[x][i];
if(vis[kind] == 0){
sub += dfs(kind);
}
else{
f[x] = kind;
}
}
unt[x] = sub;
// ob[x] = menge - unt[x] + 1;
return sub;
}
void dfs1(int x , int ins){
if(re <= 0){
return;
}
vis[x] = ins;
re--;
for(int i = 0 ; i < gr[x].size() ; i++){
int kind = gr[x][i];
if(vis[kind] == 0){
dfs1(kind , ins);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int root;
menge = n;
for(int i = 0 ;i < menge ; i++){
vis.push_back(0);
}
gru.push_back({a , 1});
gru.push_back({b , 2});
gru.push_back({c , 3});
sort(gru.begin() , gru.end());
for(int i = 0 ; i < p.size() ; i++){
gr[p[i]].push_back(q[i]);
gr[q[i]].push_back(p[i]);
}
for(int i = 0 ; i < menge ; i++){
if(gr[i].size() > 1){
root = i;
break;
}
}
dfs(root);
for(int x = 0 ; x < menge ; x++){
vis[x] = 0;
for(int i = 0 ; i < gr[x].size() ; i++ ){
int kind = gr[x][i];
if(kind == f[x]){
if(unt[x] >= gru[0].first && maxi > unt[x]){
maxi = unt[x];
pl = x;
pl2 = kind;
}
}
else{
if(menge - unt[kind] >= gru[0].first && maxi > menge - unt[kind]){
maxi = menge - unt[kind];
pl = x;
pl2 = kind;
}
}
}
}
if(maxi == mod){
return vis;
}
vis[pl] = gru[0].second;
re = gru[1].first;
dfs1( pl2 , gru[1].second );
if(re > 0){
// assert(gru[2].first >= gru[1].first && gru[1].first > gru[0].first);
for(int i = 0 ; i < menge ; i++){
vis[i] =0;
}
return vis;
}
re = gru[0].first;
dfs1(pl , gru[0].second);
for(int i = 0 ; i < menge ; i ++){
if(vis[i] == 0){
vis[i] = gru[2].second;
}
}
return vis;
}
Compilation message
split.cpp: In function 'int dfs(int)':
split.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0 ; i< gr[x].size() ; i ++){
| ~^~~~~~~~~~~~~~
split.cpp: In function 'void dfs1(int, int)':
split.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0 ; i < gr[x].size() ; i++){
| ~~^~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0 ; i < p.size() ; i++){
| ~~^~~~~~~~~~
split.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0 ; i < gr[x].size() ; i++ ){
| ~~^~~~~~~~~~~~~~
split.cpp:61:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
61 | dfs(root);
| ~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
ok, correct split |
2 |
Correct |
7 ms |
11988 KB |
ok, correct split |
3 |
Correct |
6 ms |
11984 KB |
ok, correct split |
4 |
Correct |
6 ms |
11988 KB |
ok, correct split |
5 |
Correct |
6 ms |
11988 KB |
ok, correct split |
6 |
Correct |
6 ms |
11988 KB |
ok, correct split |
7 |
Correct |
67 ms |
22648 KB |
ok, correct split |
8 |
Correct |
61 ms |
21420 KB |
ok, correct split |
9 |
Correct |
81 ms |
21056 KB |
ok, correct split |
10 |
Correct |
62 ms |
23000 KB |
ok, correct split |
11 |
Correct |
71 ms |
22944 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
ok, correct split |
2 |
Correct |
6 ms |
11964 KB |
ok, correct split |
3 |
Correct |
6 ms |
11988 KB |
ok, correct split |
4 |
Correct |
87 ms |
21536 KB |
ok, correct split |
5 |
Correct |
59 ms |
18420 KB |
ok, correct split |
6 |
Correct |
64 ms |
22904 KB |
ok, correct split |
7 |
Correct |
70 ms |
21268 KB |
ok, correct split |
8 |
Correct |
103 ms |
20616 KB |
ok, correct split |
9 |
Correct |
61 ms |
18244 KB |
ok, correct split |
10 |
Correct |
48 ms |
18628 KB |
ok, correct split |
11 |
Correct |
59 ms |
18700 KB |
ok, correct split |
12 |
Correct |
49 ms |
18708 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11952 KB |
ok, correct split |
2 |
Correct |
58 ms |
18328 KB |
ok, correct split |
3 |
Correct |
25 ms |
14528 KB |
ok, correct split |
4 |
Correct |
6 ms |
11988 KB |
ok, correct split |
5 |
Correct |
74 ms |
19832 KB |
ok, correct split |
6 |
Correct |
93 ms |
19608 KB |
ok, correct split |
7 |
Correct |
88 ms |
19668 KB |
ok, correct split |
8 |
Correct |
68 ms |
20324 KB |
ok, correct split |
9 |
Correct |
71 ms |
19708 KB |
ok, correct split |
10 |
Correct |
29 ms |
14160 KB |
ok, no valid answer |
11 |
Correct |
30 ms |
15756 KB |
ok, no valid answer |
12 |
Correct |
51 ms |
19752 KB |
ok, no valid answer |
13 |
Correct |
56 ms |
19524 KB |
ok, no valid answer |
14 |
Correct |
46 ms |
19876 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
11988 KB |
ok, correct split |
2 |
Correct |
6 ms |
12048 KB |
ok, no valid answer |
3 |
Correct |
6 ms |
11988 KB |
ok, correct split |
4 |
Correct |
7 ms |
11988 KB |
ok, correct split |
5 |
Correct |
6 ms |
11988 KB |
ok, correct split |
6 |
Correct |
8 ms |
12048 KB |
ok, correct split |
7 |
Correct |
6 ms |
11956 KB |
ok, correct split |
8 |
Correct |
8 ms |
11988 KB |
ok, correct split |
9 |
Correct |
8 ms |
12244 KB |
ok, correct split |
10 |
Incorrect |
18 ms |
12280 KB |
invalid split: #1=2, #2=1865, #3=633 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
ok, correct split |
2 |
Correct |
7 ms |
11988 KB |
ok, correct split |
3 |
Correct |
6 ms |
11984 KB |
ok, correct split |
4 |
Correct |
6 ms |
11988 KB |
ok, correct split |
5 |
Correct |
6 ms |
11988 KB |
ok, correct split |
6 |
Correct |
6 ms |
11988 KB |
ok, correct split |
7 |
Correct |
67 ms |
22648 KB |
ok, correct split |
8 |
Correct |
61 ms |
21420 KB |
ok, correct split |
9 |
Correct |
81 ms |
21056 KB |
ok, correct split |
10 |
Correct |
62 ms |
23000 KB |
ok, correct split |
11 |
Correct |
71 ms |
22944 KB |
ok, correct split |
12 |
Correct |
6 ms |
11988 KB |
ok, correct split |
13 |
Correct |
6 ms |
11964 KB |
ok, correct split |
14 |
Correct |
6 ms |
11988 KB |
ok, correct split |
15 |
Correct |
87 ms |
21536 KB |
ok, correct split |
16 |
Correct |
59 ms |
18420 KB |
ok, correct split |
17 |
Correct |
64 ms |
22904 KB |
ok, correct split |
18 |
Correct |
70 ms |
21268 KB |
ok, correct split |
19 |
Correct |
103 ms |
20616 KB |
ok, correct split |
20 |
Correct |
61 ms |
18244 KB |
ok, correct split |
21 |
Correct |
48 ms |
18628 KB |
ok, correct split |
22 |
Correct |
59 ms |
18700 KB |
ok, correct split |
23 |
Correct |
49 ms |
18708 KB |
ok, correct split |
24 |
Correct |
7 ms |
11952 KB |
ok, correct split |
25 |
Correct |
58 ms |
18328 KB |
ok, correct split |
26 |
Correct |
25 ms |
14528 KB |
ok, correct split |
27 |
Correct |
6 ms |
11988 KB |
ok, correct split |
28 |
Correct |
74 ms |
19832 KB |
ok, correct split |
29 |
Correct |
93 ms |
19608 KB |
ok, correct split |
30 |
Correct |
88 ms |
19668 KB |
ok, correct split |
31 |
Correct |
68 ms |
20324 KB |
ok, correct split |
32 |
Correct |
71 ms |
19708 KB |
ok, correct split |
33 |
Correct |
29 ms |
14160 KB |
ok, no valid answer |
34 |
Correct |
30 ms |
15756 KB |
ok, no valid answer |
35 |
Correct |
51 ms |
19752 KB |
ok, no valid answer |
36 |
Correct |
56 ms |
19524 KB |
ok, no valid answer |
37 |
Correct |
46 ms |
19876 KB |
ok, no valid answer |
38 |
Correct |
8 ms |
11988 KB |
ok, correct split |
39 |
Correct |
6 ms |
12048 KB |
ok, no valid answer |
40 |
Correct |
6 ms |
11988 KB |
ok, correct split |
41 |
Correct |
7 ms |
11988 KB |
ok, correct split |
42 |
Correct |
6 ms |
11988 KB |
ok, correct split |
43 |
Correct |
8 ms |
12048 KB |
ok, correct split |
44 |
Correct |
6 ms |
11956 KB |
ok, correct split |
45 |
Correct |
8 ms |
11988 KB |
ok, correct split |
46 |
Correct |
8 ms |
12244 KB |
ok, correct split |
47 |
Incorrect |
18 ms |
12280 KB |
invalid split: #1=2, #2=1865, #3=633 |
48 |
Halted |
0 ms |
0 KB |
- |