제출 #622558

#제출 시각아이디문제언어결과실행 시간메모리
622558JomnoiSplit the Attractions (IOI19_split)C++17
0 / 100
4 ms5204 KiB
#include <bits/stdc++.h> #include "split.h" using namespace std; const int MAX_N = 1e5 + 5; int N, M, A, B, C; int sz[MAX_N]; vector <int> graph[MAX_N]; vector <int> res; bool ok; void dfs(int u, int p, int a, int &A) { A--; res[u] = a; for(auto v : graph[u]) { if(v != p and A > 0) { dfs(v, u, a, A); } } } int dfs2(int u, int p) { if(ok == true) { return 0; } sz[u] = 1; for(auto v : graph[u]) { if(v != p) { sz[u] += dfs2(v, u); } } if(sz[u] >= A) { if(N - sz[u] >= B) { res.assign(N, 3); dfs(u, p, 1, A); dfs(p, u, 2, B); ok = true; return 0; } if(N - sz[u] >= C) { res.assign(N, 2); dfs(u, p, 1, A); dfs(p, u, 3, C); ok = true; return 0; } } if(sz[u] >= B) { if(N - sz[u] >= A) { res.assign(N, 3); dfs(u, p, 2, B); dfs(p, u, 1, A); ok = true; return 0; } if(N - sz[u] >= C) { res.assign(N, 1); dfs(u, p, 2, B); dfs(p, u, 3, C); ok = true; return 0; } } if(sz[u] >= C) { if(N - sz[u] >= A) { res.assign(N, 2); dfs(u, p, 3, C); dfs(p, u, 1, A); ok = true; return 0; } if(N - sz[u] >= B) { res.assign(N, 1); dfs(u, p, 3, C); dfs(p, u, 2, B); ok = true; return 0; } } return sz[u]; } vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) { N = n, M = p.size(), A = a, B = b, C = c; res.resize(N, 0); for(int i = 0; i < M; i++) { graph[p[i]].push_back(q[i]); graph[q[i]].push_back(p[i]); } if(M == N - 1) { dfs2(0, -1); } else { res.assign(N, 3); int rt = 0; for(int i = 0; i < N; i++) { if(graph[i].size() == 1) { rt = i; break; } } dfs(rt, -1, 2, B); for(int i = 0; i < N; i++) { if(res[i] == 0) { dfs(i, -1, 1, A); break; } } } return res; }
#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...