제출 #257752

#제출 시각아이디문제언어결과실행 시간메모리
257752maximath_1Split the Attractions (IOI19_split)C++17
100 / 100
171 ms24276 KiB
#include "split.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; vector<int> ans, disc, low, sz, par; vector<int> adj[100005], adj_st[100005]; pair<int, int> a[3]; int n, m, A, B, C, timer = 0; void init(){ a[0] = {A, 1}; a[1] = {B, 2}; a[2] = {C, 3}; sort(a, a + 3); disc.assign(n, 0); low.assign(n, 0); sz.resize(n); par.resize(n, -1); ans.assign(n, a[2].second); } void dfs(int nw){ sz[nw] = 1; disc[nw] = low[nw] = ++timer; for(int nx : adj[nw]){ if(nx != par[nw]){ if(!low[nx]){ par[nx] = nw; dfs(nx); sz[nw] += sz[nx]; low[nw] = min(low[nw], low[nx]); adj_st[nw].push_back(nx); }else{ low[nw] = min(low[nw], disc[nx]); } } } return; } int cnt, col; void fill_ans(int nw, int tp){ cnt --; ans[nw] = col; if(!tp){ for(int nx : adj_st[nw]) if(cnt) fill_ans(nx, tp); }else{ for(int nx : adj[nw]) if(cnt && ans[nx] == a[2].second) fill_ans(nx, tp); } } vector<int> find_split(int N, int _A, int _B, int _C, vector<int> P, vector<int> Q){ n = N; m = P.size(); A = _A, B = _B, C = _C; init(); for(int i = 0; i < m; i ++){ adj[P[i]].push_back(Q[i]); adj[Q[i]].push_back(P[i]); } par[0] = -1; dfs(0); int rt = 0; for(;;){ bool found = true; for(int nx : adj_st[rt]){ if(sz[nx] >= a[0].first){ found = false; rt = nx; break; } } if(found) break; } if(sz[rt] + a[1].first <= n){ cnt = a[0].first, col = a[0].second; fill_ans(rt, 0); cnt = a[1].first, col = a[1].second; fill_ans(par[rt], 1); }else{ cnt = a[1].first, col = a[1].second; ans[rt] = col; cnt --; for(int nx : adj_st[rt]) if(cnt && low[nx] < disc[rt]) //prioritize fill_ans(nx, 0); for(int nx : adj_st[rt]) if(cnt && low[nx] >= disc[rt]) fill_ans(nx, 0); cnt = a[0].first, col = a[0].second; if(par[rt] != -1) fill_ans(par[rt], 1); if(cnt) ans = vector<int> (n, 0); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...