| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 749785 | grogu | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
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"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
const ll maxn = 200005;
ll n,m;
vector<ll> g[maxn];
vector<ll> c[maxn];
vector<ll> e[maxn];
ll dsu[maxn],sz[maxn],tsz = 0;
ll x,y,xid,yid;
ll poc,col,colid;
bool ok;
ll sub[maxn];
ll par[maxn];
bool vis[maxn];
vector<ll> ans;
void dfs(ll u,ll p){
sub[u] = 1;
par[u] = p;
vis[u] = 1;
for(ll s : g[u]){
if(vis[s]) continue;
dfs(s,u);
e[u].pb(s);
e[s].pb(u);
sub[u]+=sub[s];
}
if(sub[u]>=x&&n-sub[u]>=y){
poc = u; col = x; colid = xid; ok = 1;
}
if(sub[u]>=y&&n-sub[u]>=x){
poc = u; col = y; colid = yid; ok = 1;
}
}
void dfscol(ll u,ll p,ll col,ll &z){
if(z){
ans[u] = col;
z--;
}
for(ll s : e[u]){
if(s==p) continue;
dfscol(s,u,col,z);
}
}
ll cen(ll u,ll p){
for(ll s : e[u]){
if(s==p) continue;
if(sub[s]*2>n) return cen(s,u);
}
return u;
}
void dfscomp(ll u,ll p){
dsu[u] = tsz;
sz[tsz]++;
for(ll s : e[u]){
if(s==p) continue;
dfscomp(s,u);
}
}
ll curcnt = 0;
ll use[maxn];
void dfscheck(ll u,ll st){
curcnt+=sz[u];
vis[u] = 1;
if(curcnt>=x){
use[u] = st;
ok = 1;
return;
}
for(ll s : c[u]){
if(vis[s]) continue;
dfscheck(s,st);
if(ok) return;
}
}
void dfscol2(ll u,ll col,ll &z,ll st){
ans[u] = col;
for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z);
}
void dfscol3(ll u,ll col,ll &z){
if(z) ans[u] = col,z--;
else return;
for(ll s : e[u]) if(!ans[dsu[s]]) dfscol3(s,col,z);
}
vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) {
n = N;
m = si(p);
vector<pll> v;
v.pb({A,1});
v.pb({B,2});
v.pb({C,3});
sort(all(v));
x = v[0].fi; xid = v[0].sc;
y = v[1].fi; yid = v[1].sc;
for(ll i = 1;i<=m;i++){
ll x = p[i-1] + 1;
ll y = q[i-1] + 1;
g[x].pb(y);
g[y].pb(x);
}
dfs(1,1);
ans.resize(n+1);
if(ok){
ll tmp = col;
dfscol(poc,par[poc],colid,col);
tmp^=y;
tmp^=x;
dfscol(par[poc],poc,colid^xid^yid,tmp);
for(ll i = 1;i<=n;i++){
if(ans[i]==0) ans[i] = v[2].sc;
}
reverse(all(ans));
ans.popb();
reverse(all(ans));
return ans;
}
ll root = cen(1,1);
for(ll j : e[root]){
++tsz;
dfscomp(j,root);
}
for(ll i = 1;i<=n;i++){
if(i==root) continue;
for(ll j : g[i]){
if(j==root) continue;
c[dsu[i]].pb(dsu[j]);
c[dsu[j]].pb(dsu[i]);
}
}
fill(vis,vis+1+n,0);
for(ll i = 1;i<=tsz;i++){
if(vis[i]) continue;
curcnt = 0;
dfscheck(i,i);
if(ok){poc = i; break;}
}
if(!ok){ans.popb(); return ans;}
for(ll i = 1;i<=n;i++){
if(dsu[i]==poc){
dfscol2(i,xid,x,poc);
break;
}
}
dfscol3(root,yid,y);
for(ll i = 1;i<=n;i++){
if(ans[i]==0) ans[i] = v[2].sc;
}
reverse(all(ans));
ans.popb();
reverse(all(ans));
return ans;
}
/**
6 5 2 2 2
0 1
0 2
0 3
0 4
0 5
9 10 4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
**/
#include "split.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
const ll maxn = 200005;
ll n,m;
vector<ll> g[maxn];
vector<ll> c[maxn];
vector<ll> e[maxn];
ll dsu[maxn],sz[maxn],tsz = 0;
ll x,y,xid,yid;
ll poc,col,colid;
bool ok;
ll sub[maxn];
ll par[maxn];
bool vis[maxn];
vector<ll> ans;
void dfs(ll u,ll p){
sub[u] = 1;
par[u] = p;
vis[u] = 1;
for(ll s : g[u]){
if(vis[s]) continue;
dfs(s,u);
e[u].pb(s);
e[s].pb(u);
sub[u]+=sub[s];
}
if(sub[u]>=x&&n-sub[u]>=y){
poc = u; col = x; colid = xid; ok = 1;
}
if(sub[u]>=y&&n-sub[u]>=x){
poc = u; col = y; colid = yid; ok = 1;
}
}
void dfscol(ll u,ll p,ll col,ll &z){
if(z){
ans[u] = col;
z--;
}
for(ll s : e[u]){
if(s==p) continue;
dfscol(s,u,col,z);
}
}
ll cen(ll u,ll p){
for(ll s : e[u]){
if(s==p) continue;
if(sub[s]*2>n) return cen(s,u);
}
return u;
}
void dfscomp(ll u,ll p){
dsu[u] = tsz;
sz[tsz]++;
for(ll s : e[u]){
if(s==p) continue;
dfscomp(s,u);
}
}
ll curcnt = 0;
ll use[maxn];
void dfscheck(ll u,ll st){
curcnt+=sz[u];
vis[u] = 1;
if(curcnt>=x){
use[u] = st;
ok = 1;
return;
}
for(ll s : c[u]){
if(vis[s]) continue;
dfscheck(s,st);
if(ok) return;
}
}
void dfscol2(ll u,ll col,ll &z,ll st){
ans[u] = col;
for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z);
}
void dfscol3(ll u,ll col,ll &z){
if(z) ans[u] = col,z--;
else return;
for(ll s : e[u]) if(!ans[dsu[s]]) dfscol3(s,col,z);
}
vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) {
n = N;
m = si(p);
vector<pll> v;
v.pb({A,1});
v.pb({B,2});
v.pb({C,3});
sort(all(v));
x = v[0].fi; xid = v[0].sc;
y = v[1].fi; yid = v[1].sc;
for(ll i = 1;i<=m;i++){
ll x = p[i-1] + 1;
ll y = q[i-1] + 1;
g[x].pb(y);
g[y].pb(x);
}
dfs(1,1);
ans.resize(n+1);
if(ok){
ll tmp = col;
dfscol(poc,par[poc],colid,col);
tmp^=y;
tmp^=x;
dfscol(par[poc],poc,colid^xid^yid,tmp);
for(ll i = 1;i<=n;i++){
if(ans[i]==0) ans[i] = v[2].sc;
}
reverse(all(ans));
ans.popb();
reverse(all(ans));
return ans;
}
ll root = cen(1,1);
for(ll j : e[root]){
++tsz;
dfscomp(j,root);
}
for(ll i = 1;i<=n;i++){
if(i==root) continue;
for(ll j : g[i]){
if(j==root) continue;
c[dsu[i]].pb(dsu[j]);
c[dsu[j]].pb(dsu[i]);
}
}
fill(vis,vis+1+n,0);
for(ll i = 1;i<=tsz;i++){
if(vis[i]) continue;
curcnt = 0;
dfscheck(i,i);
if(ok){poc = i; break;}
}
if(!ok){ans.popb(); return ans;}
for(ll i = 1;i<=n;i++){
if(dsu[i]==poc){
dfscol2(i,xid,x,poc);
break;
}
}
dfscol3(root,yid,y);
for(ll i = 1;i<=n;i++){
if(ans[i]==0) ans[i] = v[2].sc;
}
reverse(all(ans));
ans.popb();
reverse(all(ans));
return ans;
}
/**
6 5 2 2 2
0 1
0 2
0 3
0 4
0 5
9 10 4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
**/