#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);
| ~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
ok, correct split |
2 |
Correct |
6 ms |
11988 KB |
ok, correct split |
3 |
Correct |
6 ms |
12016 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 |
74 ms |
23108 KB |
ok, correct split |
8 |
Correct |
65 ms |
21744 KB |
ok, correct split |
9 |
Correct |
80 ms |
21364 KB |
ok, correct split |
10 |
Correct |
62 ms |
23348 KB |
ok, correct split |
11 |
Correct |
69 ms |
23280 KB |
ok, correct split |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
11972 KB |
ok, correct split |
2 |
Correct |
6 ms |
11988 KB |
ok, correct split |
3 |
Correct |
7 ms |
11988 KB |
ok, correct split |
4 |
Correct |
113 ms |
21948 KB |
ok, correct split |
5 |
Correct |
63 ms |
18796 KB |
ok, correct split |
6 |
Correct |
65 ms |
23372 KB |
ok, correct split |
7 |
Correct |
67 ms |
21696 KB |
ok, correct split |
8 |
Correct |
91 ms |
20996 KB |
ok, correct split |
9 |
Correct |
76 ms |
18744 KB |
ok, correct split |
10 |
Incorrect |
52 ms |
19104 KB |
invalid split: #1=1, #2=1, #3=99997 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
ok, correct split |
2 |
Correct |
65 ms |
18716 KB |
ok, correct split |
3 |
Correct |
29 ms |
14676 KB |
ok, correct split |
4 |
Incorrect |
7 ms |
11988 KB |
invalid split: #1=16, #2=16, #3=34 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
ok, correct split |
2 |
Incorrect |
6 ms |
11988 KB |
invalid split: #1=2, #2=1, #3=3 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
ok, correct split |
2 |
Correct |
6 ms |
11988 KB |
ok, correct split |
3 |
Correct |
6 ms |
12016 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 |
74 ms |
23108 KB |
ok, correct split |
8 |
Correct |
65 ms |
21744 KB |
ok, correct split |
9 |
Correct |
80 ms |
21364 KB |
ok, correct split |
10 |
Correct |
62 ms |
23348 KB |
ok, correct split |
11 |
Correct |
69 ms |
23280 KB |
ok, correct split |
12 |
Correct |
9 ms |
11972 KB |
ok, correct split |
13 |
Correct |
6 ms |
11988 KB |
ok, correct split |
14 |
Correct |
7 ms |
11988 KB |
ok, correct split |
15 |
Correct |
113 ms |
21948 KB |
ok, correct split |
16 |
Correct |
63 ms |
18796 KB |
ok, correct split |
17 |
Correct |
65 ms |
23372 KB |
ok, correct split |
18 |
Correct |
67 ms |
21696 KB |
ok, correct split |
19 |
Correct |
91 ms |
20996 KB |
ok, correct split |
20 |
Correct |
76 ms |
18744 KB |
ok, correct split |
21 |
Incorrect |
52 ms |
19104 KB |
invalid split: #1=1, #2=1, #3=99997 |
22 |
Halted |
0 ms |
0 KB |
- |