Submission #832131

#TimeUsernameProblemLanguageResultExecution timeMemory
832131maomao90Split the Attractions (IOI19_split)C++17
40 / 100
77 ms29260 KiB
// I can do all things through Christ who strengthens me // Philippians 4:13 #include "split.h" #include "bits/stdc++.h" using namespace std; #define REP(i, j, k) for (int i = j; i < (k); i++) #define RREP(i, j, k) for (int i = j; i >= (k); i--) template <class T> inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;} typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define SZ(x) (int) x.size() #define ALL(x) x.begin(), x.end() #define pb push_back typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef tuple<int, int, int> iii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005; const int MAXN = 200005; int n, m, s[3], ss[3]; vi adj[MAXN]; vi ans; bool ban[MAXN]; vi tree[MAXN]; void mark(int u, int p, int &rem, int x) { if (rem == 0) { return; } ans[u] = x; rem--; for (int v : tree[u]) { if (v == p || ban[v]) { continue; } mark(v, u, rem, x); } } void markall(int u, int &rem, int x) { if (rem == 0) { return; } ans[u] = x; rem--; for (int v : adj[u]) { if (ans[v] != 3) { continue; } markall(v, rem, x); } } int sub[MAXN]; int pre[MAXN], low[MAXN], ptr; void getsub(int u, int p) { sub[u] = 1; pre[u] = low[u] = ptr++; for (int v : adj[u]) { if (v == p) { continue; } if (pre[v] != -1) { mnto(low[u], pre[v]); continue; } tree[u].pb(v); tree[v].pb(u); getsub(v, u); mnto(low[u], low[v]); sub[u] += sub[v]; } } bool dfs(int u, int p) { bool bad = sub[u] < s[ss[0]] || u == 0; for (int v : tree[u]) { if (v == p) { continue; } if (sub[v] >= s[ss[0]] && n - sub[v] >= s[ss[1]]) { mark(v, u, s[ss[0]], ss[0] + 1); mark(u, v, s[ss[1]], ss[1] + 1); return 1; } bad |= sub[v] >= s[ss[0]]; if (dfs(v, u)) { return 1; } } if (bad) { return 0; } assert(sub[u] > s[ss[0]] + s[ss[2]]); int csub = sub[u]; ban[p] = 1; for (int v : tree[u]) { if (v == p) { continue; } if (low[v] < pre[u]) { ban[v] = 1; csub -= sub[v]; if (csub >= s[ss[0]] && n - csub >= s[ss[1]]) { mark(u, p, s[ss[0]], ss[0] + 1); markall(p, s[ss[1]], ss[1] + 1); assert(s[ss[1]] == 0); return 1; } } } for (int v : tree[u]) { ban[v] = 0; } return 0; } vi find_split(int n, int a, int b, int c, vi p, vi q) { ::n = n; s[0] = a; s[1] = b; s[2] = c; iota(ss, ss + 3, 0); sort(ss, ss + 3, [&] (int l, int r) { return s[l] < s[r]; }); m = SZ(p); REP (i, 0, m) { adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } ans = vi(n, ss[2] + 1); memset(pre, -1, sizeof pre); getsub(0, -1); if (dfs(0, -1)) { return ans; } swap(ss[0], ss[1]); if (dfs(0, -1)) { return ans; } ans = vi(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...