| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 253670 | TriPhan | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <split.h>
#define TASK "SPLIT"
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define F first
#define S second
#define FOR(i, a, b) for (int i=a; i<=b; i++)
#define FOr(i, a, b) for (int i=a; i<b ; i++)
#define FOD(i, a, b) for (int i=a; i>=b; i--)
#define FOd(i, a, b) for (int i=a; i>b ; i--)
#define vi vector<int>
using namespace std;
const int N=(int)1e6+7;
const int MOD=(int)1e9+7;
const ll INF=(ll)1e18+7;
vector<int> a[N];
ii A[3];
int visit[N],par[N],sz[N],ans[N],lift[N];
int m,n,T,root;
void dfs(int u) {
visit[u]=1;
sz[u]=1;
for (int v:a[u]) {
if (visit[v]) {
if (v!=par[u])
lift[u]=v;
continue;
}
par[v]=u;
dfs(v);
sz[u]+=sz[v];
}
if (sz[u] >= A[0].F && root==0)
root=u;
}
void DFS(int u,int p) {
if (A[T].F) {
A[T].F--;
ans[u]=A[T].S;
}
visit[u]=1;
for (int v:a[u])
if (v!=p && visit[v]==0)
DFS(v,u);
}
vi find_split(int n, int aa, int b, int c, vi p, vi q) {
m=sizeof(p);
A[0].F=aa;
A[1].F=b;
A[2].F=c;
A[0].S=1;
A[1].S=2;
A[2].S=3;
sort(A,A+3);
FOR(i,0,m-1) {
int u,v;
u=p[i];
v=q[i];
++u; ++v;
a[u].pb(v);
a[v].pb(u);
}
visit[1]=1;
dfs(1);
vector<int> res;
if (par[root]==0) {
FOR(i,1,n)
res.push_back(0);
return res;
}
queue<ii> Q;
for (int v:a[root])
Q.push_back({v,v});
while (n-sz[root] >= A[0].F) {
ii z=Q.back();
int v=z.F;
int r=z.S;
Q.pop();
if (visit[r]==2) continue;
if (lift[v]) {
par[v]=lift[v];
sz[root]-=sz[r];
visit[r]=2;
continue;
}
for (int u:a[v])
Q.push_back({u,r});
}
if (n-sz[root] < A[0].F) {
FOR(i,1,n)
res.push_back(0);
return res;
}
FOR(i,1,n)
a[i].clear();
FOR(i,1,n)
if (i!=root) {
a[par[i]].push_back(i);
if (par[i]!=0)
a[i].push_back(par[i]);
}
FOR(i,1,n)
visit[i]=0;
if (sz[root]>=A[1].F) {
T=1;
DFS(root,0);
T=0;
DFS(par[root],0);
}
else {
T=0;
DFS(root,0);
T=1;
DFS(par[root],0);
}
FOR(i,1,n)
if (!ans[i])
ans[i]=A[2].S;
FOR(i,1,n)
res.push_back(ans[i]);
return res;
}