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];
int p[MAXN], kol[MAXN];
int get(int x){
if(x != p[x])p[x] = get(p[x]);
return p[x];
}
void unite(int a, int b){
kol[a] += kol[b];
kol[b] = 0;
p[b] = a;
}
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(mx < 3){
int F = 0, Last = 0;
for(int i = 0; i < n; i++)if(v[i].size() == 1)F = i;
int step = 1;
vector <int> cnt(3);
cnt[0] = a;
cnt[1] = b;
cnt[2] = c;
for(int i = 0; i < n; i++){
if(i){
int New = 0;
for(auto j : v[F])if(j != Last)New = j;
Last = F;
F = New;
}
while(!cnt[step - 1])step++;
--cnt[step - 1];
res[F] = step;
}
return res;
}else if(a == 1){
queue <int> Q;
vector <bool> f(n);
int start = 0;
for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
for(int i = 0; i < n; i++)p[i] = i;
for(int i = 0; i < m; i++)if(P[i] != start && q[i] != start){
if(get(P[i]) != get(q[i]))unite(get(P[i]), get(q[i]));
}
int mx = *max_element(kol, kol + n);
if(mx >= b){
int pos = start;
kol[start] = 0;
for(int i = 0; i < n; i++)if(kol[i] > kol[pos])pos = i;
f[start] = 1;
for(int i = 0; i < n; i++){
if(P[i] == start){
if(Q.empty()){
f[q[i]] = 1;
Q.push(q[i]);
}
}
if(q[i] == start){
if(Q.empty()){
f[P[i]] = 1;
Q.push(P[i]);
}
}
}
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);
}
}
res[start] = 1;
for(auto &i : res)if(!i)i = 3;
return res;
}else if(mx >= c){
int pos = start;
kol[start] = 0;
for(int i = 0; i < n; i++)if(kol[i] > kol[pos])pos = i;
f[start] = 1;
for(int i = 0; i < n; i++){
if(P[i] == start){
if(Q.empty()){
f[q[i]] = 1;
Q.push(q[i]);
}
}
if(q[i] == start){
if(Q.empty()){
f[P[i]] = 1;
Q.push(P[i]);
}
}
}
while(!Q.empty()){
int x = Q.front();
Q.pop();
if(!c)break;
c--;
res[x] = 3;
for(auto to : v[x])if(!f[to]){
f[to] = 1;
Q.push(to);
}
}
res[start] = 1;
for(auto &i : res)if(!i)i = 2;
return res;
}else return res;
}else{
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... |