제출 #603580

#제출 시각아이디문제언어결과실행 시간메모리
603580SeDunionSplit the Attractions (IOI19_split)C++17
18 / 100
108 ms20404 KiB
#include "split.h" #include<algorithm> #include<iostream> #include<vector> #include<assert.h> using namespace std; const int N = 2e5 + 123; vector<int>g[N]; int used[N]; int n, a, b, c; vector<int>vec, ans; int av = -1, bv = -1; int tin[N], tout[N], timer, sz[N]; void dfs(int v) { used[v] = 1; sz[v] = 1; tin[v] = timer++; for (int to : g[v]) if (!used[to]) { dfs(to); sz[v] += sz[to]; if (av == -1 && sz[to] >= a && n - sz[to] >= a) { av = to, bv = v; } if (av == N && sz[to] >= a && n - sz[to] >= a) { av = v, bv = -to; } } tout[v] = timer++; } bool cmp(int a, int b) { return tin[a] < tin[b]; } bool upper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int gg[4]; vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p, vector<int> q) { n = n_, a = a_, b = b_, c = c_; if (a > b) swap(a, b); if (b > c) swap(b, c); if (a > b) swap(a, b); if (a_ == a && b_ == b && c_ == c) gg[1] = 1, gg[2] = 2, gg[3] = 3; if (a_ == a && b_ == c && c_ == b) gg[1] = 1, gg[3] = 2, gg[2] = 3; if (a_ == b && b_ == a && c_ == c) gg[2] = 1, gg[1] = 2, gg[3] = 3; if (a_ == b && b_ == c && c_ == a) gg[2] = 1, gg[3] = 2, gg[1] = 3; if (a_ == c && b_ == a && c_ == b) gg[3] = 1, gg[1] = 2, gg[2] = 3; if (a_ == c && b_ == b && c_ == a) gg[3] = 1, gg[2] = 2, gg[1] = 3; // a <= b <= c // a <= n/3 ? // b <= n/2 ? int m = p.size(); for (int i = 0 ; i < m ; ++ i) { g[p[i]].emplace_back(q[i]); g[q[i]].emplace_back(p[i]); } ans = vector<int>(n, 3); if (n <= 2500 && m <= 5000) { for (int q = 0 ; q < n ; ++ q) { for (int i = 0 ; i < n ; ++ i) used[i] = 0; dfs(q); if (av != -1) { if (bv < 0) { bv = -bv; for (int i = 0 ; i < n ; ++ i) used[i] = 0; dfs(bv); } vector<int>vec; for (int i = 0 ; i < n ; ++ i) { vec.emplace_back(i); } sort(vec.begin(), vec.end(), cmp); for (int v : vec) { if (a>0 && upper(av, v)) { ans[v] = 1, a--; } if (b>0 && !upper(av, v)) { ans[v] = 2, b--; } } for (int &i : ans) i = gg[i]; return ans; } } return vector<int>(n, 0); } dfs(0); if (av == -1) return vector<int>(n, 0); if (bv < 0) { bv = -bv; for (int i = 0 ; i < n ; ++ i) used[i] = 0; dfs(bv); } vector<int>vec; for (int i = 0 ; i < n ; ++ i) { vec.emplace_back(i); } sort(vec.begin(), vec.end(), cmp); for (int v : vec) { if (a>0 && upper(av, v)) { ans[v] = 1, a--; } if (b>0 && !upper(av, v)) { ans[v] = 2, b--; } } for (int &i : ans) i = gg[i]; 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...