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 "split.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
inline void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
const int MAXN = 100055;
const int MAXM = 200055;
vector<int> G[MAXN];
int cnt[MAXN];
int A[MAXM], B[MAXM];
bitset<MAXN> chk;
int ud[MAXN];
int Ans[MAXN];
int N, M, CA, CB, CC, CO[4], Rt;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
void normdfs(int i, int &c, int key) {
if(!c) return;
chk[i] = false; c--; Ans[i] = key;
for(int v : G[i]) if(chk[v]) normdfs(v, c, key);
}
bool normAns() {
for(int i = 0; i < N; i++) G[i].clear();
for(int i = 0; i < M; i++) fg(G, A[i], B[i]);
chk.reset();
for(int i = 0; i < N; i++)
if(Ans[i] < 1 || 2 < Ans[i]) Ans[i] = 3;
int x = -1;
for(int i = 0; i < N; i++) if(1 == Ans[i]) { x = i; chk[i] = true; }
if(chk.count() < CA) return false;
{ int c = CA; normdfs(x, c, -1); }
for(int i = 0; i < N; i++) {
if(1 == Ans[i]) Ans[i] = 3;
else if(-1 == Ans[i]) Ans[i] = 1;
}
chk.reset();
for(int i = 0; i < N; i++) if(2 == Ans[i]) { x = i; chk[i] = true; }
if(chk.count() < CB) return false;
{ int c = CB; normdfs(x, c, -2); }
for(int i = 0; i < N; i++) {
if(2 == Ans[i]) Ans[i] = 3;
else if(-2 == Ans[i]) Ans[i] = 2;
}
return true;
}
void predfs(int i) {
cnt[i] = 1;
for(int v : G[i]) if(!cnt[v]) {
predfs(v);
cnt[i] += cnt[v];
}
}
void cent(int &rt) {
const int N = cnt[rt];
for(int hi, hc;;) {
hi = hc = -1;
for(int v : G[rt]) if(cnt[v] < cnt[rt] && hc < cnt[v]) {
hi = v; hc = cnt[v];
}
if(hc*2 <= N) break;
cnt[rt] = N - hc;
cnt[hi] = N;
rt = hi;
}
}
void treedfs(int i) {
Ans[i] = 1;
for(int v : G[i]) if(cnt[v] < cnt[i])
treedfs(v);
}
bool solveTree() {
for(int v : G[Rt]) if(CA <= cnt[v]) {
fill(Ans, Ans+N, 2);
treedfs(v);
return true;
}
return false;
}
void solve() {
iota(CO, CO+4, 0);
if(CA > CB) { swap(CA, CB); swap(CO[1], CO[2]); }
if(CA > CC) { swap(CA, CC); swap(CO[1], CO[3]); }
if(CB > CC) { swap(CB, CC); swap(CO[2], CO[3]); }
iota(ud, ud+MAXN, 0);
for(int i = 0, a, b; i < M; i++) {
a = A[i]; b = B[i];
if(uf(a) == uf(b)) continue;
uf(a, b);
fg(G, a, b);
}
predfs(0); cent(Rt);
if(solveTree()) return;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
::N = n; ::M = sz(p);
::CA = a; ::CB = b; ::CC = c;
for(int i = 0; i < ::M; i++) {
::A[i] = p[i];
::B[i] = q[i];
}
solve();
if(!normAns()) return vector<int>(::N, 0);
vector<int> res;
for(int i = 0; i < ::N; i++) {
if(1 == ::Ans[i]) res.eb(::CO[1]);
else if(2 == ::Ans[i]) res.eb(::CO[2]);
else res.eb(::CO[3]);
}
return res;
}
Compilation message (stderr)
split.cpp: In function 'bool normAns()':
split.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(chk.count() < CA) return false;
~~~~~~~~~~~~^~~~
split.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(chk.count() < CB) return false;
~~~~~~~~~~~~^~~~
# | 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... |