제출 #405642

#제출 시각아이디문제언어결과실행 시간메모리
405642Tc14Split the Attractions (IOI19_split)C++17
22 / 100
691 ms1048580 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include "split.h" using namespace std; #define ve vector typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9 + 10; int n, v1, v2; pii x, y, z, curr; bool valid; ve<ve<int>> T; ve<int> Ans; int dfs(int u, int p) { int s = 1; for (int v : T[u]) { if (v != p) { s += dfs(v, u); } } if (s < n - s) { if (s >= x.first && n - s >= y.first) { v1 = u; v2 = p; valid = true; } } else { if (n - s >= x.first && s >= y.first) { v1 = p; v2 = u; valid = true; } } return s; } void assign(int u, int p, int b) { if (curr.first > 0) { Ans[u] = curr.second; curr.first--; } for (int v : T[u]) { if (v != p && v != b) { assign(v, u, b); } } } ve<int> find_split(int _n, int a, int b, int c, ve<int> p, ve<int> q) { int m; n = _n; T = ve<ve<int>>(n); m = (int)p.size(); for (int i = 0; i < m; i++) { T[p[i]].push_back(q[i]); T[q[i]].push_back(p[i]); } ve<pii> A = {{a, 1}, {b, 2}, {c, 3}}; sort(A.begin(), A.end()); x = A[0]; y = A[1]; z = A[2]; valid = false; dfs(0, -1); if (valid) { Ans = ve<int>(n, z.second); curr = x; assign(v1, -1, v2); curr = y; assign(v2, -1, v1); } else Ans = ve<int>(n, 0); 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...