제출 #417985

#제출 시각아이디문제언어결과실행 시간메모리
417985usachevd0Split the Attractions (IOI19_split)C++14
40 / 100
144 ms26596 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "split.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const int maxN = 1e5 + 5; int n; vector<int> G[maxN], T[maxN], H[maxN]; bool used[maxN]; int comp[maxN], comps, csz[maxN], cfirst[maxN]; bool cused[maxN]; bool forA[maxN]; int dfs1(int v, int &c, int p = -1) { int sz = 1; used[v] = 1; for (int u : G[v]) { if (used[u] && u != p) continue; T[v].push_back(u); if (u == p) continue; sz += dfs1(u, c, v); } if (c == -1 && 2 * sz >= n) c = v; return sz; } void dfs2(int v, int c, int p = -1) { comp[v] = c; if (++csz[c] == 1) cfirst[c] = v; for (int u : T[v]) if (u != p) dfs2(u, c, v); } vector<int> find_split(int _n, int A, int B, int C, vector<int> eu, vector<int> ev) { int m = eu.size(); n = _n; int sizes[3] = {A, B, C}; int sord[3] = {0, 1, 2}; sort(sord, sord + 3, [&](int i, int j) -> bool { return sizes[i] < sizes[j]; }); A = sizes[sord[0]], B = sizes[sord[1]]; for (int i = 0; i < m; ++i) { int u = eu[i], v = ev[i]; G[u].push_back(v); G[v].push_back(u); } int c = -1; dfs1(0, c); if (c == -1) c = 0; comps = 0; comp[c] = -1; for (int v : T[c]) { dfs2(v, comps++, c); } // debug(c); // mdebug(comp, n); // for (int v = 0; v < n; ++v) // for (int u : T[v]) // if (v < u) // debug(v, u); // mdebug(csz, comps); if (*max_element(csz, csz + comps) >= A) { // cerr << "easy" << endl; int cl = max_element(csz, csz + comps) - csz; int v = cfirst[cl]; vector<int> ans(n, 0); int need; function<void(int, int, int)> dfs = [&](int v, int c, int p) { if (need <= 0) return; --need; ans[v] = c; for (int u : T[v]) if (u != p) dfs(u, c, v); }; need = A; dfs(v, sord[0] + 1, c); need = B; dfs(c, sord[1] + 1, v); for (int& x : ans) if (x == 0) x = sord[2] + 1; return ans; } for (int i = 0; i < m; ++i) { int u = eu[i], v = ev[i]; if (u == c || v == c || comp[u] == comp[v]) continue; H[comp[u]].push_back(comp[v]); H[comp[v]].push_back(comp[u]); } for (int c = 0; c < comps; ++c) { if (!cused[c]) { int sz = 0; function<void(int)> dfsc = [&](int c) { cused[c] = 1; sz += csz[c]; for (int d : H[c]) if (!cused[d]) dfsc(d); }; dfsc(c); if (sz >= A) { int need = A; fill(cused, cused + comps, 0); function<void(int)> dfsc = [&](int c) { if (need <= 0) return; need -= csz[c]; cused[c] = 1; forA[c] = 1; for (int d : H[c]) if (!cused[d]) dfsc(d); }; dfsc(c); vector<int> ans(n, 0); function<void(int)> dfsa = [&](int v) { if (need <= 0) return; --need; used[v] = 1; ans[v] = sord[0] + 1; for (int u : G[v]) if (!used[u] && u != c && forA[comp[u]]) dfsa(u); }; need = A; fill(used, used + n, 0); dfsa(cfirst[c]); function<void(int)> dfsb = [&](int v) { if (need <= 0) return; --need; used[v] = 1; ans[v] = sord[1] + 1; for (int u : G[v]) if (!used[u] && !forA[comp[u]]) dfsb(u); }; need = B; fill(used, used + n, 0); dfsb(c); for (int& x : ans) if (x == 0) x = sord[2] + 1; return ans; } } } return vector<int>(n, 0); } #ifdef LOCAL int main() { #ifdef LOCAL freopen("in", "r", stdin); #endif int n, m, a, b, c; assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c)); vector<int> p(m), q(m); for (int i=0; i<m; i++) assert(2 == scanf("%d%d", &p[i], &q[i])); fclose(stdin); vector<int> result = find_split(n, a, b, c, p, q); for (int i=0; i<(int)result.size(); i++) printf("%s%d", ((i>0)?" ":""), result[i]); printf("\n"); fclose(stdout); return 0; } #endif
#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...