제출 #480545

#제출 시각아이디문제언어결과실행 시간메모리
480545couplefireSplit the Attractions (IOI19_split)C++17
100 / 100
154 ms40780 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, m, k, id[N], siz[N], rt; vector<int> adj[N], tadj[N], nadj[N], comps[N], orda; vector<pair<int, int>> bruh; bool vis[N]; void get_tree(int v){ vis[v] = 1; siz[v] = 1; for(auto u : adj[v]) if(!vis[u]) tadj[v].push_back(u), tadj[u].push_back(v), get_tree(u), siz[v] += siz[u]; } int get_centroid(){ int p = -1, v = 0; do{ int nxt = -1; for(auto u : tadj[v]) if(u!=p && 2*siz[u]>n) nxt = u; p = v, v = nxt; } while(~v); return p; } void get_label(int v, int p, int idx){ comps[idx].push_back(v); id[v] = idx; for(auto u : tadj[v]) if(u!=p) get_label(u, v, idx); } void get_orda(int v){ vis[v] = 1; orda.push_back(v); for(auto u : adj[v]) if(!vis[u]) get_orda(u); } vector<int> get_ans(vector<int> a0){ memset(vis, 0, sizeof vis); for(auto x : a0) vis[x] = 1; for(int i = 0; i<n; ++i) if(!vis[i]){get_orda(i); break;} vector<int> ans(n, bruh[2].second); while((int)a0.size()>bruh[0].first) orda.push_back(a0.back()), a0.pop_back(); for(auto x : a0) ans[x] = bruh[0].second; for(int i = 0; i<bruh[1].first; ++i) ans[orda[i]] = bruh[1].second; return ans; } bool find_good(int v, int& cur){ vis[v] = 1; cur += comps[v].size(); orda.push_back(v); if(cur>=bruh[0].first) return 1; for(auto u : nadj[v]) if(!vis[u]){ bool tmp = find_good(u, cur); if(tmp) return 1; } return 0; } vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> _p, vector<int> _q){ n = _n, m = _p.size(); bruh.push_back({_a, 1}); bruh.push_back({_b, 2}); bruh.push_back({_c, 3}); sort(bruh.begin(), bruh.end()); for(int i = 0; i<m; ++i) adj[_p[i]].push_back(_q[i]), adj[_q[i]].push_back(_p[i]); get_tree(0); rt = get_centroid(); k = tadj[rt].size(); for(int i = 0; i<k; ++i) get_label(tadj[rt][i], rt, i); id[rt] = -1; for(int i = 0; i<k; ++i) if((int)comps[i].size()>=bruh[0].first) return get_ans(comps[i]); for(int i = 0; i<m; ++i){ int u = id[_p[i]], v = id[_q[i]]; if(u==v || u==-1 || v==-1) continue; nadj[u].push_back(v); nadj[v].push_back(u); } memset(vis, 0, sizeof vis); for(int i = 0; i<k; ++i){ if(vis[i]) continue; int tot = 0; if(find_good(i, tot)){ vector<int> a0; for(auto x : orda) a0.insert(a0.end(), comps[x].begin(), comps[x].end()); orda.clear(); return get_ans(a0); } else{ orda.clear(); } } vector<int> ans(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...