제출 #389729

#제출 시각아이디문제언어결과실행 시간메모리
389729SuhaibSawalha1Split the Attractions (IOI19_split)C++17
40 / 100
124 ms14428 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> adj; vector<bool> vis; int n, m; vector<int> ord, k, ans; void dfs (int u) { vis[u] = 1; for (int v : adj[u]) { if (!vis[v]) { dfs(v); } } ord.push_back(u); } void go (int i) { while (k[i]) { --k[i]; ans[ord.back()] = i + 1; ord.pop_back(); } } void color (int u, int p, int c) { if (k[c] && !ans[u]) { ans[u] = c + 1; --k[c]; } else { return; } for (int v : adj[u]) { if (v ^ p) { color(v, u, c); } } } int dfs2 (int u, int p = -1) { int s = 1; for (int v : adj[u]) { if (v ^ p) { s += dfs2(v, u); } } for (int i = 0; i < 3; ++i) { if (k[i] && s >= k[i]) { color(u, p, i); return 0; } } return s; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { ::n = n; k = {a, b, c}; m = p.size(); adj.resize(n); ans.resize(n); vis.resize(n); for (int i = 0; i < m; ++i) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } array<int, 2> P[n]; for (int i = 0; i < n; ++i) { P[i] = {(int)adj[i].size(), i}; } sort(P, P + n); if (m == n - 1) { dfs2(P[n - 1][1]); if (count(k.begin(), k.end(), 0) < 2) { return vector<int>(n, 0); } for (int i = 0; i < n; ++i) { if (!ans[i]) { ord.push_back(i); } } } else { dfs(P[0][1]); } for (int i = 0; i < 3; ++i) { go(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...