| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 490214 | 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.
/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/
#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=2e5+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;
ll anc[maxn];
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);
adj1[to].pb(u);
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];
void dfs1(ll u,ll col1)
{
if (cnt[col1]<val[col1])
{
}
else
{
col1=colmx;
}
ans[u]=col1;
cnt[col1]++;
// assert(cnt[col1]<=val[col1]);
for (auto to:adj1[u])
{
if (to==anc[u]||ans[to]) continue;
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:adj1[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 <<cl<<endl;
for (int i=0;i<adj1[u].size();i++)
{
ll to=adj1[u][i];
if (to==anc[u]) continue;
if (low[to]<num[u])
{
if (cl-siz[to]>=nw[0].ff)
{
// cout <<to<<" chk"<<endl;
h+=siz[to];
cl-=siz[to];
dfs1(to,nw[1].ss);
}
else
{
// cout <<"nah"<<endl;
dfs1(u,nw[0].ss);
break;
}
}
else
{
dfs1(to,nw[0].ss);
}
}
// cout <<h<<endl;
if (h<nw[1].ss)
{
ans=vector<ll> (n,0);
return ans;
}
if (anc[u]!=-1)
{
dfs2(anc[u],nw[1].ss);
}
for (int i=1;i<=3;i++)
{
// cout <<cnt[i]<<" "<<val[i]<<endl;
assert(cnt[i]==val[i]);
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
vector<ll> ans=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
/*vector<ll> ans= find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
for (auto to:ans) cout <<to<<" ";
cout <<endl;*/
}*/