Submission #292496

#TimeUsernameProblemLanguageResultExecution timeMemory
292496miss_robotSplit the Attractions (IOI19_split)C++14
22 / 100
119 ms11312 KiB
#include <bits/stdc++.h> #include "split.h" #pragma GCC optimize("O3") using namespace std; const int N = 1e5; int n, A, B, C, ia, ib, ic, d; int st[N]; vector<int> g[N], sol; void flood1(int u, int &c, int f){ if(sol[u] || !c) return; else sol[u] = f, c--; for(int v : g[u]) flood1(v, c, f); } void st1(){ flood1(0, A, ia); for(int i = 0; i < n; i++){ if(!sol[i]){ flood1(i, B, ib); break; } } for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic; } void st2(){ flood1(0, B, ib); for(int i = 0; i < n; i++){ if(sol[i]) continue; if(A) sol[i] = ia, A--; else sol[i] = ib; } } void flood2(int u, int p, int &c, int f){ if(!c) return; sol[u] = f, c--; for(int v : g[u]) if(v != p) flood2(v, u, c, f); } void dfs(int u, int p){ st[u] = 1; for(int v : g[u]){ if(v == p) continue; dfs(v, u); if(d) return; st[u] += st[v]; } if(n-st[u] >= A && st[u] >= B){ flood2(u, p, B, ib); flood2(p, u, A, ia); for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic; d = 1; } else if(st[u] >= A && n-st[u] >= B){ flood2(u, p, A, ia); flood2(p, u, B, ib); for(int i = 0; i < n; i++) if(!sol[i]) sol[i] = ic; d = 1; } } void st3(){ dfs(0, 0); } void tmp(int tn){ n = tn; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){ int m = p.size(); for(int i = 0, u, v; i < m; i++){ u = p[i], v = q[i]; g[u].push_back(v); g[v].push_back(u); } A = a, B = b, C = c, ia = 1, ib = 2, ic = 3; if(C < B) swap(B, C), swap(ib, ic); if(B < A) swap(A, B), swap(ia, ib); if(C < B) swap(B, C), swap(ib, ic); sol.resize(n); tmp(n); if(m == n-1) st3(); else if(A == 1) st2(); else st1(); return sol; }
#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...