제출 #972033

#제출 시각아이디문제언어결과실행 시간메모리
972033opPOSplit the Attractions (IOI19_split)C++14
40 / 100
58 ms17748 KiB
#include "split.h" #include <bits/stdc++.h> #define sz(x) (int)x.size() #define all(x) (x).begin(), (x).end() using namespace std; void dfs(int v, vector<vector<int>> &g, vector<bool> &used, vector<int> &vec, int need) { if (sz(vec) >= need) return; if (used[v]) return; used[v] = 1; vec.push_back(v); for (int &u : g[v]) { if (used[u]) continue; dfs(u, g, used, vec, need); } } void tree(int v, vector<vector<int>> &g, vector<int> &siz, int p = -1) { siz[v] = 1; for (int &u : g[v]) { if (u == p) continue; tree(u, g, siz, v); siz[v] += siz[u]; } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m = sz(p); vector<int> res(n); vector<int> deg(n); vector<vector<int>> g(n); for (int i = 0; i < m; i++) { deg[p[i]]++; deg[q[i]]++; g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); } int vert = 0; for (int i = 0; i < n; i++) { if (deg[i] < deg[vert]) { vert = i; } } vector<int> v = {0, a, b, c}; vector<int> perm = {1, 2, 3}; sort(all(perm), [&](int i, int j){ return v[i] < v[j]; }); vector<bool> used(n); if (m == n - 1) { vector<int> siz(n); tree(0, g, siz); vector<int> A, B, C; for (int i = 0; i < m; i++) { int x = p[i], y = q[i]; if (siz[x] > siz[y]) { swap(x, y); } if (siz[x] < n - siz[x]) { if (siz[x] >= v[perm[0]] && n - siz[x] >= v[perm[1]]) { used[y] = 1; dfs(x, g, used, A, v[perm[0]]); used[y] = 0; dfs(y, g, used, B, v[perm[1]]); for (int ver = 0; ver < n; ver++) { if (!used[ver]) { C.push_back(ver); } } break; } } else { if (n - siz[x] >= v[perm[0]] && siz[x] >= v[perm[1]]) { used[y] = 1; dfs(x, g, used, B, v[perm[1]]); used[y] = 0; dfs(y, g, used, A, v[perm[0]]); for (int ver = 0; ver < n; ver++) { if (!used[ver]) { C.push_back(ver); } } break; } } } if (sz(A) != v[perm[0]] || sz(B) != v[perm[1]] || sz(C) != v[perm[2]]) return res; for (int &i : A) { res[i] = perm[0]; } for (int &i : B) { res[i] = perm[1]; } for (int &i : C) { res[i] = perm[2]; } return res; } vector<int> A; dfs(vert, g, used, A, v[perm[0]]); assert(sz(A) == v[perm[0]]); for (int &i : A) { res[i] = perm[0]; } int unused = -1; for (int v = 0; v < n; v++) { if (!used[v]) { unused = v; } } assert(unused != -1); vector<int> B; dfs(unused, g, used, B, v[perm[1]]); assert(sz(B) == v[perm[1]]); for (int &i : B) { res[i] = perm[1]; } for (int i = 0; i < n; i++) { if (!used[i]) { res[i] = perm[2]; } } return res; } /* 9 10 4 2 3 0 1 0 2 0 3 0 4 0 6 0 8 1 7 3 7 4 5 5 6 */ /* 6 5 2 2 2 0 1 0 2 0 3 0 4 0 5 */ /* 3 2 1 1 1 0 1 0 2 */ /* 12 11 6 4 2 0 1 0 2 0 3 0 4 0 5 1 6 2 7 2 8 3 9 3 10 3 11 */ /* g++ -std=gnu++14 -O2 -Wall -pipe -static -o "split" "grader.cpp" "split.cpp" */
#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...