| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 737170 | ammar2000 | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define dp st
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=3e5+7;
ll INF=8e18+7;
int MOD=1e9+7;
vector<int> ret;
bool fou=0;
vector <ll> v[SI];
int nn, aa,bb,cc;
int p[SI],st[SI];
void bt(int x=1,int pa=0)
{
p[x]=pa;
st[x]=1;
for(auto i:v[x])
{
if (i==pa)
continue;
bt(i,x);
st[x]+=st[i];
}
}
int hmtc=0;
void dfs(int x,int pa ,int col)
{
if (hmtc<=0)
return ;
ret[x-1]=col;
hmtc--;
for(auto i:v[x])
if(i!=pa)
dfs(i,x,col);
}
void bld(int x,int i,int o,bool k)
{
if (fou)
return ;
fou=1;
int re;
vector <ll> ss(2),ee(2);
if (o==0)
ss={bb,cc},ee={2,3},re=1;
else if (o==1)
ss={aa,cc},ee={1,3},re=2;
else ss={bb,cc},ee={1,2},re=3;
if (k)
swap(ss[0],ss[1]),swap(ee[0],ee[1]);
hmtc=ss[0];
dfs(i,x,ee[0]);
hmtc=ss[1];
dfs(x,i,ee[1]);
for(int i=0;i<nn;i++)
if(ret[i]==0)
ret[i]=re;
}
void fans(int x=1,int pa=0)
{
if (x!=1)
{st[pa]-=st[x];
st[x]+=st[pa];}
// cout <<x<<" " <<pa <<"\n";
for (int o=0;o<3;o++)
{
vector <ll> ss(2);
if (o==0)
ss={bb,cc};
else if (o==1)
ss={aa,cc};
else ss={bb,cc};
for (auto i:v[x])
{
// cout << dp[i]<<" " <<ss[0]<<" " <<dp[x]<<" " <<ss[1]<<"\n";
if (dp[i]>=ss[0]&&dp[x]-dp[i]>=ss[1])
bld(x,i,o,0);
else if (dp[i]>=ss[1]&&dp[x]-dp[i]>=ss[1])
bld(x,i,o,1);
}
}
for(auto i:v[x])
if (i!=pa)
fans(i,x);
if (x!=1)
{st[x]-=st[pa];
st[pa]+=st[x];
}
}
bool rrk=0;
void dfsc(int x=n,int pa=v[n][0])
{
if (x==n&&rrk)
return ;
rrk=1;
if (aa>0)
{
ret[x-1]=1;
aa--;
}
else if (bb>0)
{
ret[x-1]=2;
bb--;
}
else
{
ret[x-1]=3;
cc--;
}
for(auto i:v[x])
if (i!=pa)
dfsc(i,x);
}
int isvis[SI];
void dfsa(int x=1)
{
isvis[x]=1;
if (bb==0)
return ;
ret[x-1]=2;
bb--;
for(auto i:v[x])
if (isvis[i]==0)
dfsa(i);
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
ret.resize(n);
for(int i=0;i<p.size();i++)
{
int d=p[i],m=q[i];
d++;
m++;
v[d].pb(m);
v[m].pb(d);
}
aa=a;
bb=b;
cc=c;
nn=n;
if (n==p.size()+1)
{bt();
fans();}
else if (a==1)
{
dfsa();
int u=1;
for(int i=0;i<n;i++)
{
if (ret[i]==0)
ret[i]=u,u=min(u+2,3);
}
}
else
{
dfsc();
}
return ret;
}