| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 152396 | crackersamdjam | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
using namespace std;
const int MM = 1e5+2;
vector<int> adj[MM];
vector<int> ans;
int sz[MM], dfn[MM], low[MM], t, par[MM];
int a, b, c, first = -1, purple;
int aa = 1, ab = 2, ac = 3;
void fill(int cur, int &rem, int v){
//printf("f "); print(cur, rem, v);
if(!rem || ans[cur])
return;
ans[cur] = v;
rem--;
for(int u: adj[cur]){
if(dfn[u] > dfn[cur] && low[u] >= dfn[cur])
fill(u, rem, v);
}
}
void free_fill(int cur, int &rem, int v){
//printf("ff "); print(cur, rem, v);
if(!rem || ans[cur])
return;
ans[cur] = v;
rem--;
for(int u: adj[cur]){
free_fill(u, rem, v);
}
}
void fill_down(int cur, int &rem, int v){
//printf("fd "); print(cur, rem, v);
if(!rem || ans[cur])
return;
ans[cur] = v;
rem--;
for(int u: adj[cur]){
if(dfn[u] > dfn[cur])
fill_down(u, rem, v);
}
}
int dfs(int cur, int pre){
print(cur, pre);
if(cur)
par[cur] = pre;
sz[cur] = 1;
dfn[cur] = low[cur] = ++t;
for(int u: adj[cur]){
if(u == pre)
continue;
if(!dfn[u]){
sz[cur] += dfs(u, cur);
low[cur] = min(low[cur], low[u]);
}
else
low[cur] = min(low[cur], dfn[u]);
}
if(first == -1 && sz[cur] >= a){
//printf("do %d\n", cur);
for(int u: adj[cur]){
if(dfn[u] > dfn[cur] && low[u] >= dfn[cur]){
purple += sz[u];
}
}
if(purple > b+c)
return first = -2;
first = cur;
}
return sz[cur];
}
vector<int> find_split(int n, int ia, int ib, int ic, vector<int> p, vector<int> q){
a = ia, b = ib, c = ic;
ans.resize(n);
for(int i = 0; i < p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
if(a > b)
swap(a, b), swap(aa, ab);
if(b > c)
swap(b, c), swap(ab, ac);
if(a > b)
swap(a, b), swap(aa, ab);
assert(a <= b && b <= c);
//print(a, b, c, aa, ab, ac);
dfs(0, -1);
fflush(stdout);
assert(first != -1);
if(first == -2)
return ans;
if(purple >= b){
fill(first, b, ab);
free_fill(par[first], a, aa);
}
else{
fill(first, a, aa);
for(int u: adj[first]){
if(u != par[first])
fill_down(u, a, aa);
}
//printf("a %d\n", a);
assert(a == 0);
free_fill(par[first], b, ab);
}
assert(a == 0);
assert(b == 0);
for(int &i: ans){
if(!i)
i = ac;
}
return ans;
}
#ifndef ONLINE_JUDGE
vector<int> a5, a6;
int main(){
//auto out = find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5}, {1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
//auto out = find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
//for(int i: out)
// printf("%d ", i);
/*
int a1, a11, a2, a3, a4;
scan(a1, a11, a2, a3, a4);
a5.resize(a11);
a6.resize(a11);
for(int i = 0; i < a1; i++)
scan(a5[i]);
for(int i = 0; i < a1; i++)
scan(a6[i]);
auto out = find_split(a1, a2, a3, a4, a5, a6);
for(int i: out)
printf("%d ", i);
*/
return 0;
}
#endif
/*
* tree
* make sure that a subtree is larger than smallest [a, b, c]
* the second smallest can go through centroid
* and remaining nodes go to largeststd::vector<int> find_split(int n, int a, int b, int c, std::vector<int>p, std::vector<int>q)
*
* policija tarjan dfs tree to get dfn and low
* if(size[u] >= a)
* if dfn[v] > dfn[u] && low[v] >= dfn[u]
*
* if purple > b+c
* impossible
* if purple >= b
* make it b
* else make it a
* borrow red while needed
* take children of u
*/