| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1201094 | Kaang | Split the Attractions (IOI19_split) | C++20 | 0 ms | 0 KiB |
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) v.begin(), v.end()
using namespace std;
int dpt[100001],sz[100001],sp[100001],cnt,num[100001],p[100001],vst[100001],cnta,cntb,ta,tb,tp;
vector <int> v[100001],g[100001];
priority_queue <pii> pq;
vector <int> ans;
int dfs(int node,int par)
{
cnt++;
num[node]=cnt;
sp[node]=cnt;
sz[node]=1;
p[node]=par;
for(auto cur:v[node])
{
if(cur==par)
continue;
else if(!dpt[cur])
{
g[node].push_back(cur);
dpt[cur]=dpt[node]+1;
sp[node]=min(sp[node],dfs(cur,node));
sz[node]+=sz[cur];
}
else
{
sp[node]=min(sp[node],num[cur]);
}
}
return sp[node];
}
void fdfs(int node,int f)
{
if(vst[node])
return;
else
{
vst[node]=f;
for(auto cur:v[node])
fdfs(cur,f);
}
}
void adfs(int node,int f)
{
if(vst[node]!=f||ans[node]!=0)
return;
else
{
if(cnta<ta&&vst[node]==f)
ans[node]=f,cnta++;
for(auto cur:g[node])
adfs(cur,f);
}
}
void bdfs(int node,int f)
{
if(vst[node]!=f||ans[node]!=0)
return;
else
{
if(cntb<tb&&vst[node]==f)
ans[node]=f,cntb++;
for(auto cur:g[node])
bdfs(cur,f);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m=p.size();
ans.resize(n,0);
if(a<=b&&b<=c)
tp=1;
else if(a<=c&&c<b)
tp=2;
else if(c<a&&a<=b)
tp=3;
else if(b<a&&a<=c)
tp=4;
else if(b<=c&&c<a)
tp=5;
else if(c<b&&b<a)
tp=6;
if(a>b)
swap(a,b);
if(a>c)
swap(a,c);
if(b>c)
swap(b,c);
ta=a,tb=b;
for(int i=0;i<m;i++)
{
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
dpt[0]=1;
dfs(0,-1);
int dt1=0,dt2=0;//dt1이면 해 존재, dt2면 해 구성 불가, 판별필요 없음
for(int i=0;i<n;i++)
{
int mx1=0,mx2=0,lft=n-1;
for(int cur:g[i])
{
if(sp[cur]>=num[i])
{
int szcur=sz[cur];
lft-=szcur;
if(szcur>=mx1)
{
mx2=mx1;
mx1=szcur;
}
else if(szcur<mx1&&szcur>=mx2)
{
mx2=szcur;
}
}
}
if(lft>=mx1)
{
mx2=mx1;
mx1=lft;
}
else if(lft<mx1&&lft>=mx2)
{
mx2=lft;
}
if(mx1>=b&&n-mx1>=a)
{
dt1=1;
vst[i]=1;
if(lft==mx1)
{
fdfs(p[i],2);
for(int cur:g[i])
{
fdfs(cur,1);
}
}
else
{
for(int cur:g[i])
{
if(sz[cur]==mx1)
{
fdfs(cur,2);
break;
}
}
for(int cur:g[i])
{
fdfs(cur,1);
}
}
break;
}
else if(mx1>=b&&n-mx1<a)
continue;
else if(mx1<b&&mx2<a)
{
dt2=1;
break;
}
else if(mx1<b&&mx2>=a)
{
dt1=1;
vst[i]=2;
if(lft==mx2)
{
fdfs(p[i],1);
for(int cur:g[i])
{
fdfs(cur,2);
}
}
else
{
for(int cur:g[i])
{
if(sz[cur]==mx2)
{
fdfs(cur,1);
break;
}
}
for(int cur:g[i])
{
fdfs(cur,2);
}
}
break;
}
}
if(dt2)
return ans;
else if(dt1)
{
for(int i=0;i<n;i++)
{
if(vst[i]==1)
adfs(i,1);
else
bdfs(i,2);
}
for(int i=0;i<n;i++)
{
if(ans[i]==0)
ans[i]=3;
}
for(int i=0;i<n;i++)
{
if(tp==1)
ans[i]=ans[i];
else if(tp==2)
{
if(ans[i]==2)
ans[i]=3;
else if(ans[i]==3)
ans[i]=2;
}
else if(tp==3)
{
if(ans[i]==1)
ans[i]=3;
else if(ans[i]==2)
ans[i]=1;
else if(ans[i]==3)
ans[i]=2;
}
else if(tp==4)
{
if(ans[i]==1)
ans[i]=2;
else if(ans[i]==2)
ans[i]=1;
else
ans[i]=3;
}
else if(tp==5)
{
if(ans[i]==1)
ans[i]=2;
else if(ans[i]==2)
ans[i]=3;
else
ans[i]=1;
}
else
{
if(ans[i]==1)
ans[i]=3;
else if(ans[i]==2)
ans[i]=2;
else
ans[i]=1;
}
}
return ans;
}
else
{
int cura=0;
pq.push({1,0});
while(cura<a)
{
int node=pq.top().se;
pq.pop();
if(vst[node]==0)
{
vst[node]=1;
cura++;
int lft=n-1;
for(int cur:g[node])
{
if(sp[cur]>=num[node])
{
lft-=sz[node];
if(sz[cur]<a)
{
fdfs(cur,1);
cura+=sz[cur];
}
}
}
if(lft<a)
{
fdfs(p[node],1);
cura+=lft;
}
for(int cur:v[node])
{
if(vst[cur]==0)
pq.push({dpt[cur],cur});
}
if(vst[par[node]]==0)
pq.push({dpt[p[node]],par[node]});
}
}
for(int i=0;i<n;i++)
{
if(vst[i]!=1)
vst[i]=2;
}
for(int i=0;i<n;i++)
{
if(vst[i]==1)
adfs(i,1);
else
bdfs(i,2);
}
for(int i=0;i<n;i++)
{
if(ans[i]==0)
ans[i]=3;
}
for(int i=0;i<n;i++)
{
if(tp==1)
ans[i]=ans[i];
else if(tp==2)
{
if(ans[i]==2)
ans[i]=3;
else if(ans[i]==3)
ans[i]=2;
}
else if(tp==3)
{
if(ans[i]==1)
ans[i]=3;
else if(ans[i]==2)
ans[i]=1;
else if(ans[i]==3)
ans[i]=2;
}
else if(tp==4)
{
if(ans[i]==1)
ans[i]=2;
else if(ans[i]==2)
ans[i]=1;
else
ans[i]=3;
}
else if(tp==5)
{
if(ans[i]==1)
ans[i]=2;
else if(ans[i]==2)
ans[i]=3;
else
ans[i]=1;
}
else
{
if(ans[i]==1)
ans[i]=3;
else if(ans[i]==2)
ans[i]=2;
else
ans[i]=1;
}
}
return ans;
}
}