#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x)
#define p2(x,y)
#define pp(x)
#define pv(x)
#define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;
vector<vector<int> > adj(N);
vector<int> res;
bool v[N];
pi siz[3];
int cnt[N];
void dfs(int s, int e){
cnt[s] = 1;
for(auto x : adj[s])
if(x!=e){
dfs(x,s);
cnt[s] += cnt[x];
}
}
int curr;
int now;
void color(int s, int e){
if(now+1>siz[curr-1].F)return;
res[s] = siz[curr-1].S;
now++;
for(auto x : adj[s])
if(x!=e){
color(x,s);
}
}
void solve(int s, int e){
bool flag = false;
vector<int> go;
for(auto x : adj[s])
if(x!=e && cnt[x]>=siz[curr-1].F){
flag = true;
solve(x,s);
cnt[s] -= cnt[x];
if(curr==3)return;
}
else if(x!=e)
go.push_back(x);
if(cnt[s] >= siz[curr-1].F){
res[s] = siz[curr-1].S;
now = 1;
for(auto x : go)
color(x,s);
curr++;
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
siz[0] = {a,1};
siz[1] = {b,2};
siz[2] = {c,3};
sort(siz,siz+3);
swap(siz[0],siz[1]);
int i;
for(i=0;i<p.size();i++){
int x = p[i],y = q[i];
adj[x].push_back(y);
adj[y].push_back(x);
}
res.assign(n,0);
dfs(0,0);
curr = 1;
solve(0,0);
if(curr<3){
for(auto &x : res)
x = 0;
return res;
}
for(auto &x : res)
if(x==0)x = siz[curr-1].S;
return res;
}
/*
11 10
3 5 3
0 1
1 3
1 4
1 5
4 6
0 2
2 7
2 8
7 9
9 10
*/
Compilation message
split.cpp: In function 'void solve(int, int)':
split.cpp:61:10: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
61 | bool flag = false;
| ^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:90:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(i=0;i<p.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
ok, correct split |
| 2 |
Runtime error |
724 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
ok, correct split |
| 2 |
Runtime error |
626 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
ok, correct split |
| 2 |
Incorrect |
87 ms |
11000 KB |
invalid split: #1=9317, #2=40000, #3=50683 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
637 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
ok, correct split |
| 2 |
Runtime error |
724 ms |
1048580 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
