Submission #1243200

#TimeUsernameProblemLanguageResultExecution timeMemory
1243200rayan_bdSplit the Attractions (IOI19_split)C++20
0 / 100
610 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() const int mxN = 1e5 + 100; vector<int> adj[mxN]; int par[mxN], sz[mxN], nby2; vector<int> ans; int find(int u){ return par[u] = (u == par[u] ? u : find(par[u])); } bool unite(int u, int v){ u = find(u), v = find(v); if(u == v) return 0; par[u] = v; return 1; } void calc_sz(int u = 0, int par = -1){ sz[u] = 1; for(auto it : adj[u]){ if(it ^ par){ calc_sz(it, u); sz[u] += sz[it]; } } } int get_sz(int u, int par){ int ans = 1; for(auto it : adj[u]){ if(it ^ par) continue; ans += get_sz(it, u); } return ans; } int get_cent(int u = 0, int par = -1){ int mx = -1; for(auto it : adj[u]){ if(it ^ par){ if(mx == -1) mx = it; else if(sz[mx] < sz[it]) mx = it; } } if(sz[mx] >= nby2){ return get_cent(mx, u); } return u; } int done = 0; void work(int u, int par, int cc, int lstc){ if(done <= 0) ans[u] = lstc; else ans[u] = cc; for(auto it : adj[u]){ if(it ^ par){ work(it, u, cc, lstc); } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m = (int) p.size(); ans.resize(n, -1); vector<pair<int, int>> ord = {{a, 1}, {b, 2}, {c, 3}}; sort(all(ord)); nby2 = n / 2; for(int i = 0; i < n; ++i) par[i] = i; for(int i = 0; i < m; ++i){ if(unite(p[i], q[i])){ adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } } calc_sz(); int cent = get_cent(); for(auto it : adj[cent]){ if(get_sz(it, cent) >= ord[0].fi){ done = ord[0].fi; work(it, cent, ord[0].se, ord[2].se); done = ord[1].fi; work(cent, it, ord[1].se, ord[2].se); break; } } for(int i = 0; i < n; ++i){ if(ans[i] == -1){ for(int j = 0; j < n; ++j) ans[j] = 0; break; } } 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...