# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
960533 | 2024-04-10T15:27:47 Z | vjudge1 | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KB |
#include "split.h" #include <bits/stdc++.h> #define ll long long using namespace std; #define pb push_back const int N = 1e5 + 10; vector<int> g1[N]; vector<int> g2[N]; bool vis[N]; int v = -1; int dfs(int x){ vis[x] = 1; int sz = 1; for(auto u : g1[x]){ if(!vis[u]){ sz += dfs(u); g2[x].pb(u); } } if(v != -1)return sz; if(sz >= f[0].first && n - sz >= f[1].first){ v = x; } return sz; } int n; int res[N]; pair<int,int> f[3]; void dfsa(int x){ if(!f[0].first)return; res[x] = f[0].second; f[0].first--; for(auto u : g2[x]){ if(!res[u]){ dfsa(u); } } } void dfsb(int x){ if(!f[1].first)return; res[x] = f[1].second; f[1].first--; for(auto u : g2[x]){ if(!res[u]){ dfsb(u); } } } vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) { n = nn; f[0] = {a, 1}; f[1] = {b, 2}; f[2] = {c, 3}; sort(f, f + 3); for(int i = 0;i<p.size();i++){ g1[p[i]].pb(q[i]); } vector<int> ans(n , 0); dfs(0); if(v == -1)return ans; dfsa(v); dfsb(0); for(int i = 0;i<n;i++){ if(!res[i])res[i] =f[2].second; ans[i] = res[i]; } return ans; }