제출 #645240

#제출 시각아이디문제언어결과실행 시간메모리
645240LeonaRagingSplit the Attractions (IOI19_split)C++14
40 / 100
122 ms30768 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back #define db(val) "[" #val " = " << (val) << "] " const ll mod = 1e9 + 7; const int maxn = 1e5 + 4; const int INF = 1e9; int n, m, cnt, node[maxn]; int tin[maxn], tout[maxn], low[maxn], sz[maxn], res[maxn]; vector<int> adj[maxn], g[maxn]; map<int,int> bad; pair<int,int> req[5]; bool ok = false; void dfs1(int u, int p) { tin[u] = low[u] = ++tin[0]; node[tin[0]] = u; sz[u] = 1; for (int v : adj[u]) { if (v == p) continue; if (!tin[v]) { dfs1(v, u); sz[u] += sz[v]; g[u].pb(v); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], tin[v]); } tout[u] = tin[0]; } void dfs3(int u, int p, int col) { // to mau // if (col == 2) clog << u << ' '; if (cnt == req[col].fi) return; res[u] = col; cnt++; for (int v : adj[u]) if (!bad[v] && v != p && res[v] == 3) dfs3(v, u, col); } void dfs2(int u, int p) { if (ok) return; bool flag = true; for (int v : g[u]) if (v != p) { dfs2(v, u); if (sz[v] >= req[1].fi) flag = false; } if (flag && sz[u] >= req[1].fi) { int rem = n - sz[u]; if (rem < req[1].fi) { bad.clear(); for (int v : g[u]) if (low[v] < tin[u] && rem < req[1].fi) { rem += sz[v]; bad[v] = 1; } } if (rem >= req[1].fi) { for (int i = 1; i <= n; i++) res[node[i]] = 3; int col1 = 1, col2 = 2; if (rem < req[2].fi) swap(col1, col2); dfs3(u, p, col1); bad.clear(); cnt = 0; dfs3(p, 0, col2); ok = true; } } } vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) { n = _n, m = p.size(); req[1] = {a, 1}; req[2] = {b, 2}; req[3] = {c, 3}; sort(req + 1, req + 4); for (int i = 0; i < m; i++) { int u = p[i], v = q[i]; u++, v++; adj[u].pb(v); adj[v].pb(u); } dfs1(1, 0); dfs2(1, 0); vector<int> ans(n); for (int i = 0; i < n; i++) ans[i] = req[res[i + 1]].se; return ans; } // int main() // { // ios::sync_with_stdio(0); // cin.tie(0); cout.tie(0); // //freopen(".INP", "r", stdin); // //freopen(".OUT", "w", stdout); // int n, m, a, b, c; // vector<int> p, q; // cin >> n >> m >> a >> b >> c; // for (int i = 1; i <= m; i++) { // int u, v; cin >> u >> v; // p.pb(u); q.pb(v); // } // vector<int> ans = find_split(n, a, b, c, p, q); // for (auto i : ans) // cout << i << ' '; // }
#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...