제출 #830460

#제출 시각아이디문제언어결과실행 시간메모리
830460pavementSplit the Attractions (IOI19_split)C++17
0 / 100
593 ms1048576 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back int sz[100005], par[100005], out[100005]; bool vis[100005]; vector<int> adj[100005]; int get_sz(int u, int e = -1) { sz[u] = 1; for (auto v : adj[u]) if (v != e) { par[v] = u; sz[u] += get_sz(v, u); } return sz[u]; } void mark_all(int u, int col, int e = -1) { out[u] = col; for (auto v : adj[u]) if (v != e) { mark_all(v, col, u); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m = (int)p.size(); for (int i = 0; i < m; i++) { adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } get_sz(0); int root = -1, split_point = -1; for (int i = 0; i < n; i++) { for (auto [d, col] : {mp(&a, 1), mp(&b, 2), mp(&c, 3)}) { if (sz[i] == *d) { root = 0; split_point = i; mark_all(i, col, par[i]); *d = 0; goto break_out; } if (n - sz[i] == *d) { root = i; split_point = par[i]; mark_all(par[i], col, i); *d = 0; goto break_out; } } } break_out:; if (root == -1) { return vector<int>(n, 0); } queue<int> Q; vis[root] = 1; Q.push(root); int cnt = 1; if (cnt == max({a, b, c})) { for (int i = 0; i < n; i++) { if (vis[i]) { out[i] = max({mp(a, 1), mp(b, 2), mp(c, 3)}).second; } } goto done; } while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto v : adj[u]) if (!vis[v] && v != split_point) { vis[v] = 1; Q.push(v); cnt++; if (cnt == max({a, b, c})) { for (int i = 0; i < n; i++) { if (vis[i]) { out[i] = max({mp(a, 1), mp(b, 2), mp(c, 3)}).second; } } goto done; } } } done:; set<int> used; for (int i = 0; i < n; i++) { if (out[i]) { used.insert(out[i]); } } assert((int)used.size() == 2); int tmp = 0; for (int i : used) { tmp ^= i; } for (int i = 0; i < n; i++) { if (out[i] == 0) { out[i] = tmp; } } vector<int> real_out; for (int i = 0; i < n; i++) { real_out.pb(out[i]); } return real_out; }
#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...