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 start;
bool f[N];
void dfs(int x, int pr){
if(f[x] == 1){
start = x;
return;
}
if(f[x] == 2)return;
f[x] = 1;
for(auto to : v[x])if(to != pr)dfs(to, x);
f[x] = 2;
}
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;
start = 0;
// for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
// if(v[start].size() != 1){
// dfs(1, 0);
// }
q.push(start);
vector <bool> f(n);
f[start] = 1;
res[start] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
if(x != start){
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] = 3;
return res;
}else 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{
return res;
}
return res;
}
Compilation message (stderr)
split.cpp: In function 'void dfs(int, int)':
split.cpp:27:13: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
if(f[x] == 2)return;
~~~~~^~~~
# | 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... |