| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 198416 | FerThugGato12500 | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<split.h>
using namespace std;
vector<int> ed[100001];
int need[3];
int n, m;
bool vis[100001];
int cld[100001];
int dfs(int ind)
{
int D=1;
vis[ind]=true;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]])
D+=dfs(ed[ind][i]);
return (cld[ind] = D);
}
int bus(int ind)
{
bool z=true;
vis[ind]=true;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]] && cld[ed[ind][i]]>=n/2)
z=false;
if(n-cld[ind]>=n/2)
z=false;
if(z) return ind;
int D=-1;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]])
D=max(bus(ed[ind][i]), D);
return D;
}
int centroide()
{
dfs(1);
memset(vis, false, sizeof(vis));
return bus(1);
}
vector<int> ans[3];
int rey;
typedef struct
{
int to, cld;
}Wasd;
bool operator < (const Wasd &a, const Wasd &b)
{
return a.cld < b.cld;
}
void expand(int ind)
{
vis[ind]=true;
ans[rey].push_back(ind);
if(ans[rey].size()==need[rey])
return;
vector<Wasd> ed2;
Wasd te;
for(int i = 0; i < ed[ind].size(); i++)
{
te.to=ed[ind][i];
te.cld=cld[te.to]-cld[ind];
if(te.cld<0) te.cld=cld[te.to];
ed2.push_back(te);
}
sort(ed2.begin(), ed2.end());
for(int i = 0; i < ed2.size(); i++)
if(!vis[ed2[i].to] && ans[rey].size()<need[rey])
expand(ed2[i].to);
return;
}
int res[100001];
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
n=N; need[0]=a; need[1]=b; need[2]=c;
m=p.size();
int x, y;
for(int i = 0; i < m; i++)
{
x=p[i]; y=q[i];
ed[x].push_back(y);
ed[y].push_back(x);
}
int cnt = centroide();
if(need[0]<=max(need[1], need[2]) && need[0]>=min(need[2], need[1]))
rey=0;
else if(need[1]<=max(need[0], need[2]) && need[1]>=min(need[2], need[0]))
rey=1;
else rey=2;
memset(vis, false, sizeof(vis));
expand(cnt);
if(need[0]<=need[1] && need[0]<=need[2])
rey=0;
else if(need[1]<=need[0] && need[1]<=need[2])
rey=1;
else rey=2;
for(int i = 0; i < n; i++)
if(!vis[i])
{
expand(i);
if(ans[rey].size()==need[rey])
break;
ans[rey].clear();
}
for(int k = 0; k < 3; k++)
for(int i = 0; i < ans[k].size(); i++)
res[ans[k][i]]=k+1;
if(ans[0].size()>0 && ans[1].size()>0)
rey=2;
else if(ans[1].size()>0 && ans[2].size()>0)
rey=0;
else rey=1;
for(int i = 0; i < n; i++)
if(res[i]==0)
res[i] = rey+1;
vector<int> find_split(vector<int> respuesta);
for(int i = 0; i < n; i++)
respuesta.push_back(res[i]);
return respuesta;
}