| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 816966 | vjudge1 | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
vi G[100100], children[100100];
bool vis[100100];
int A, B, C, N, timer = 0, tez[100100], tag[100100], low[100100];
vi ret;
bool found = false, special[100100];
void dfs2(int at, int tip, int &cnt){
if(cnt > 0){
cnt--;
ret[at] = tip;
}
else{
ret[at] = 3;
}
for(auto next:children[at]){
dfs2(next, tip,cnt);
}
}
void dfs3(int at,int tip,int &cnt){
if(cnt > 0){
cnt--;
ret[at] = tip;
}
else{
ret[at] = 3;
}
for(auto next:G[at]){
if(ret[next] == 0){
dfs3(next,tip,cnt);
}
}
}
void dfs(int at){
tag[at] = low[at] = ++timer;
tez[at] = 1;
for(auto next:G[at]){
if(tag[next] == 0){
dfs(next);
children[at].pb(next);
tez[at] += tez[next];
low[at] = min(low[at],low[next]);
}
else{
low[at] = min(low[at],tag[next]);
}
}
if(found){
return ;
}
if(tez[at] >= A){
int tmp = tez[at];
for(auto next:children[at]){
if(low[next] < tag[at] && tmp - tez[next] >= A){
tmp -= tez[next];
special[next] = true;
}
}
if(tmp >= A && N- tmp >= B){
found = true;
int need = A-1;
ret[at] = 1;
for(auto next:children[at]){
if(special[next] == true){
continue;
}
dfs2(next,1,need );
}
need = B;
dfs3(0,2,need);
}
else if(tmp >= B && N - tmp >= A){
found = true;
int need = B - 1;
ret[at] = 2;
for(auto next:children[at]){
if(special[next] == true){
continue;
}
dfs2(next,2,need);
}
need= A;
dfs3(0,1,need);
}
}
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
vi put = {0, 1, 2, 3};
if(b < a){
swap(a, b);
swap(put[1], put[2]);
}
else if(c < a){
swap(a, c);
swap(put[1], put[3]);
}
if(b > c){
swap(b, c);
swap(put[2], put[3]);
}
A = a; B = b; C = c; N = n;
ret.resize(n,0);
for(int i = 0; i < (int)q.size(); i++){
G[p[i]].pb(q[i]);
G[q[i]].pb(i);
}
dfs(0);
for(int i = 0; i < n; i++){
ret[i] = put[ret[i]];
}
return ret;
}