| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 490274 | fcmalkcin | Split the Attractions (IOI19_split) | C++17 | 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 <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=1e5+50;
const ll mod=1e9+7 ;
const ll base=2e18;
/// you will be the best but now you just are trash
/// goal 6/7
vector<ll> adj[maxn];
vector<pll> nw;
vector<ll> adj1[maxn];
ll siz[maxn];
ll low[maxn];
ll num[maxn];
ll cntnw=0;
ll pos=-1;
void dfs(ll u)
{
cntnw++;
low[u]=cntnw;
num[u]=cntnw;
siz[u]=1;
bool chk=true;
for (auto to:adj[u])
{
if (num[to])
{
low[u]=min(low[u],num[to]);
continue;
}
adj1[u].pb(to);
anc[to]=u;
// cout <<u<<" "<<to<<" chk1"<<endl;
dfs(to);
low[u]=min(low[u],low[to]);
siz[u]+=siz[to];
if (siz[to]<nw[0].ff)
{
}
else
{
chk=false;
}
}
if (chk&&siz[u]>=nw[0].ff)
{
pos=u;
}
}
vector<ll> ans;
ll colmx;
ll cnt[4];
ll val[4];
ll dem=0;
void dfs1(ll u,ll col1)
{
// cout <<siz[u]<<" chk"<<endl;
if (cnt[col1]<val[col1])
{
}
else
{
col1=colmx;
}
ans[u]=col1;
cnt[col1]++;
// assert(cnt[col1]<=val[col1]);
for (auto to:adj1[u])
{
dfs1(to,col1);
}
}
void dfs2(ll u,ll col2)
{
if (cnt[col2]<val[col2])
{
}
else
{
col2=colmx;
}
ans[u]=col2;
cnt[col2]++;
// assert(cnt[col2]<=val[col2]);
for (auto to:adj[u])
{
if (ans[to]) continue;
dfs2(to,col2);
}
}
vector<ll> find_split(int n, int a, int b, int c, vector<ll> p, vector<ll> q)
{
memset(anc,-1,sizeof(anc));
nw.pb(make_pair(a,1));
nw.pb(make_pair(b,2));
nw.pb(make_pair(c,3));
sort(nw.begin(),nw.end());
for (int i=1;i<=nw.size();i++) val[nw[i-1].ss]=nw[i-1].ff;
colmx=nw.back().ss;
for (int i=0;i<p.size();i++)
{
adj[p[i]].pb(q[i]);
adj[q[i]].pb(p[i]);
}
ans=vector<ll> (n,0);
dfs(0);
// cout <<pos<<endl;
assert(pos!=-1);
ll cl=siz[pos];
ll u=pos;
ll h=n-cl;
// cout <<h<<" "<<cl<<endl;
ll kp=nw[0].ff;
for (int i=0;i<adj1[u].size();i++)
{
ll to=adj1[u][i];
if (to==anc[u]) continue;
// cout <<"wTF"<<" "<<to<<" "<<u<<" "<<anc[u]<<endl;
if (low[to]<num[u])
{
// cout <<"WTF"<<endl;
if (cl-siz[to]>=kp)
{
// cout <<"WYF"<<endl;
h+=siz[to];
cl-=siz[to];
}
else
{
// cout <<"nah"<<endl;
break;
}
}
else
{
}
}
// cout <<h<<" "<<nw[1].ff<<endl;
if (h<nw[0].ff)
{
ans=vector<ll> (n,0);
return ans;
}
// cout <<h<<" "<<cl<<" "<<pos<<" "<<adj1[pos].size()<<" "<<siz[pos]<<endl;
if (h<cl)
{
swap(nw[0],nw[1]);
// cout <<"na"<<endl;
}
cl=siz[pos];
h=n-cl;
// cout <<h<<" "<<cl<<endl;
ans[pos]=nw[0].ss;
cnt[nw[0].ss]++;
// cout <<cnt[1]<<" "<<cnt[2]<<" "<<cnt[3]<<endl;
for (int i=0;i<adj1[u].size();i++)
{
ll to=adj1[u][i];
// cout <<"wTF"<<" "<<to<<" "<<u<<" "<<anc[u]<<endl;
if (low[to]<num[u])
{
// cout <<"WTF"<<endl;
if (cl-siz[to]>=kp)
{
h+=siz[to];
cl-=siz[to];
}
else
{
// cout <<"nah"<<endl;
for (int j=i;j<adj1[u].size();j++)
{
ll to=adj1[u][j];
dfs1(to,nw[0].ss);
}
break;
}
}
else
{
//cout <<" wtf"<<endl;
dfs1(to,nw[0].ss);
}
}
//cout <<nw[1].ss<<" "<<cnt[2]<<" "<<val[2]<<" "<<cnt[3]<<" "<<val[3]<<endl;
if (anc[u]!=-1)
{
dfs2(anc[u],nw[1].ss);
}
for (int i=1;i<=3;i++)
{
// cout <<cnt[i]<<" "<<val[i]<<endl;
if (cnt[i]!=val[i])
{
cout <<-1;
}
// assert(cnt[i]==val[i]);
// cout <<-1;
}
// ans=vector<ll> (n,1);
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
// freopen("test.", "w", stdout);
}
if (1)
{
ll n, a, b, c;
ll m;
cin>> n>> m;
cin>> a>> b>> c;
vector<ll> vt;
vector<ll> vt1;
for (int i=1;i<=m;i++)
{
ll x, y;
cin>>x>> y;
vt.pb(x);
vt1.pb(y);
}
vector<ll> ans=find_split(n,a,b,c, vt,vt1);
}
else
{
vector<ll> ans=find_split(3,1,1,1, {0,0},{2,1});
}
}*/