제출 #1067899

#제출 시각아이디문제언어결과실행 시간메모리
1067899Gromp15Split the Attractions (IOI19_split)C++17
40 / 100
1592 ms21896 KiB
#include <bits/stdc++.h> #include "split.h" #define ll long long #define ar array #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rint(l, r) uniform_int_distribution<int>(l, r)(rng) vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { vector<vector<int>> adj(n); int m = sz(p); for (int i = 0; i < m; i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } if (m == n-1) { vector<int> sub(n), p(n, -1); auto dfs = [&](auto&& s, int v) -> void { sub[v] = 1; for (int u : adj[v]) if (u != p[v]) { p[u] = v; s(s, u); sub[v] += sub[u]; } }; dfs(dfs, 0); ar<int, 3> size{a, b, c}; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) { int other = 3 - i - j; for (int k = 0; k < n; k++) if (sub[k] >= size[i] && n - sub[k] >= size[j]) { vector<int> col(n, other+1); auto color = [&](auto&& s, int v, int P, int& left, int who) -> void { if (!left) return; col[v] = who; left--; for (int u : adj[v]) if (u != P) s(s, u, v, left, who); }; color(color, k, p[k], size[i], i+1); color(color, p[k], k, size[j], j+1); return col; } } return vector<int>(n); } for (int t = 0; t < 5; t++) { for (int i = 0; i < n; i++) shuffle(all(adj[i]), rng); for (int r = 0; r < n; r++) { vector<int> sub(n), p(n, -1); vector<bool> vis(n); vector<vector<int>> adj2(n); auto dfs = [&](auto&& s, int v) -> void { sub[v] = 1, vis[v] = 1; for (int u : adj[v]) if (!vis[u]) { p[u] = v; adj2[u].push_back(v); adj2[v].push_back(u); s(s, u); sub[v] += sub[u]; } }; dfs(dfs, r); ar<int, 3> size{a, b, c}; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (i != j) { int other = 3 - i - j; for (int k = 0; k < n; k++) if (sub[k] >= size[i] && n - sub[k] >= size[j]) { vector<int> col(n, other+1); auto color = [&](auto&& s, int v, int P, int& left, int who) -> void { if (!left) return; col[v] = who; left--; for (int u : adj2[v]) if (u != P) s(s, u, v, left, who); }; color(color, k, p[k], size[i], i+1); color(color, p[k], k, size[j], j+1); return col; } } } } return vector<int>(n); }
#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...