Submission #997833

#TimeUsernameProblemLanguageResultExecution timeMemory
997833biankSplit the Attractions (IOI19_split)C++14
11 / 100
560 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) int(x.size()) const int MAX_N = 1e5; vector<int> adj[MAX_N]; void dfs(int u, vector<int> &vis, int &b, int color, int p = -1) { if (!b) return; vis[u] = color; b--; for (int v : adj[u]) if (v != p) { if (vis[v] != color) dfs(v, vis, b, color, u); } } int sz[MAX_N], par[MAX_N]; int getSize(int u, int p = -1) { par[u] = p, sz[u] = 1; for (int v : adj[u]) if (v != p) { sz[u] += getSize(v, u); } return sz[u]; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int color[3] = {1, 2, 3}; if (a > b) { swap(a, b); swap(color[0], color[1]); } if (a > c) { swap(a, c); swap(color[0], color[3]); } if (b > c) { swap(b, c); swap(color[1], color[2]); } for (int i = 0; i < sz(p); i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } vector<int> ans(n, color[2]); if (a == 1) { dfs(0, ans, b, color[1]); for (int i = 0; i < n; i++) { if (ans[i] == color[2]) { ans[i] = color[0]; break; } } return ans; } getSize(0); int u = 0; for (int i = 1; i < n; i++) { if (sz[i] >= a && sz[i] < sz[u]) u = i; } if (n - sz[u] < a) return vector<int>(n, 0); dfs(u, ans, a, color[0], par[u]); dfs(par[u], ans, b, color[1], u); 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...