This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "split.h"
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
vector <int> v[MAXN];
ll t[MAXN], P[MAXN];
void dfs(ll x, ll pr){
P[x] = pr;
t[x] = 1;
for(auto to : v[x])if(to != pr){
t[x] += t[to];
dfs(to, x);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m = p.size(), mx = 0;
for(int i = 0; i < m; i++){
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
mx = max(mx, (int)v[p[i]].size());
mx = max(mx, (int)v[q[i]].size());
}
vector <int> res(n);
if(a == 1){
queue <int> q;
int start = 0;
q.push(start);
vector <bool> f(n);
f[start] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
if(!b)break;
b--;
res[x] = 2;
for(auto to : v[x])if(!f[to]){
f[to] = 1;
q.push(to);
}
}
for(int i = 0; i < n; i++)if(res[i] == 0){res[i] = 1; break;}
for(int i = 0; i < n; i++)if(res[i] == 0)res[i] = 3;
return res;
}else{
int start = 0;
for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
vector <ll> cnt(3);
vector <bool> f(n);
cnt[0] = a;
cnt[1] = b;
cnt[2] = c;
vector <ll> p(3);
p[0] = 1;
p[1] = 2;
p[2] = 3;
for(int i = 0; i < 3; i++)
for(int j = i + 1; j < 3; j++)if(cnt[p[i] - 1] > cnt[p[j] - 1])swap(p[i], p[j]);
dfs(start, 0ll);
for(int i = 0; i < n; i++)if(t[i] >= cnt[p[0] - 1] && n - t[i] >= cnt[p[1] - 1]){
queue <int> q;
f[i] = 1;
f[P[i]] = 1;
res[P[i]] = p[0];
cnt[p[0] - 1]--;
q.push(P[i]);
while(!q.empty()){
int x = q.front();
q.pop();
res[x] = p[0];
for(auto to : v[x])if(!f[to] && cnt[p[0] - 1]){
cnt[p[0] - 1]--;
q.push(to);
}
}
res[i] = p[1];
cnt[p[0] - 1]--;
q.push(i);
while(!q.empty()){
int x = q.front();
q.pop();
res[x] = p[1];
for(auto to : v[x])if(!f[to] && cnt[p[1] - 1]){
cnt[p[1] - 1]--;
q.push(to);
}
}
for(auto &j : res)if(j == 0)j = p[2];
return res;
}
return res;
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |