#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
const int MX=3e5, MOD=1e9+7;
int n, m, a[4], root=0;
int rsa[4], sa[4], val[4];
vi p, q;
vi chl[MX], adj[MX];
int sz[MX], parent[MX], split=-1;
vi ans;
bitset<MX> visited, p1;
int p1Size=0;
void dfsChl(int u=0, int p=-1) {
if(visited[u]) return;
visited[u] = 1;
parent[u] = p;
if(p != -1) chl[p].pb(u);
for(int v:adj[u])
dfsChl(v, u);
}
int dfsSz(int u=0) {
sz[u] = 1;
for(int v:chl[u])
sz[u] += dfsSz(v);
return sz[u];
}
void dfsSplit(int u=0) {
int mxSz=0;
for(int v:chl[u]) mxSz=max(mxSz, sz[v]);
if(sz[u] >= a[1] && mxSz < a[1])
split = u;
for(int v:chl[u])
dfsSplit(v);
}
void dfsP1(int u) {
p1[u]=1;
for(int v:chl[u])
dfsP1(v);
}
void dfsP1Rev(int u) {
p1[u]=0;
for(int v:chl[u])
dfsP1Rev(v);
}
bool dfsP2(int u) {
bool conp2=0;
for(int v:adj[u])
if(!p1[v])
conp2=1;
if(conp2) {
if(p1Size - sz[u] < a[1]) {
return 1;
} else {
p1Size -= sz[u];
dfsP1Rev(u);
}
} else {
for(int v:chl[u])
if(dfsP2(v))
return 1;
}
return 0;
}
void dfsFillAns(int u, bool g, int c) {
if(p1[u] != g) return;
if(visited[u]) return;
visited[u] = 1;
if(a[c] != 0)
ans[u] = c, a[c]--;
for(int v:adj[u])
dfsFillAns(v, g, c);
}
void find_split_5() {
visited.reset();
dfsChl();
dfsSz();
dfsSplit();
p1.reset();
dfsP1(split);
p1Size = sz[split];
for(int v:chl[split]) {
if(dfsP2(v)) {
dfsFillAns(split, 1, 1);
dfsFillAns(parent[split], 0, 2);
return;
}
}
if(n - p1Size < a[1]) {
//not possible
RE(i,n) ans[i] = 0;
} else {
dfsFillAns(split, 1, 1);
dfsFillAns(parent[split], 0, 2);
}
}
vi find_split(int N, int A, int B, int C, vi P, vi Q) {
val[1]=A, val[2]=B, val[3]=C;
RE1(i,3) sa[i]=i;
sort(sa+1, sa+4, [](int i, int j) {
return val[i]<val[j];
});
RE1(i,3) rsa[sa[i]] = i;
rsa[0] = 0;
n=N, p=P, q=Q;
RE1(i,3) a[i] = val[sa[i]];
m = p.size();
ans.assign(n, 3);
RE(i,m) adj[p[i]].pb(q[i]), adj[q[i]].pb(p[i]);
find_split_5();
RE(i,n) ans[i] = rsa[ans[i]];
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14464 KB |
invalid split: #1=0, #2=0, #3=3 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14464 KB |
invalid split: #1=0, #2=0, #3=3 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14464 KB |
invalid split: #1=0, #2=0, #3=5 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14464 KB |
invalid split: #1=0, #2=9, #3=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
14464 KB |
invalid split: #1=0, #2=0, #3=3 |
| 2 |
Halted |
0 ms |
0 KB |
- |
