제출 #1047688

#제출 시각아이디문제언어결과실행 시간메모리
1047688MercubytheFirstSplit the Attractions (IOI19_split)C++14
11 / 100
53 ms10072 KiB
#include <bits/stdc++.h> #include "split.h" using namespace std; vector<signed> find_split(signed n, signed a, signed b, signed c, vector<signed> p, vector<signed> q) { vector<signed> res(n); vector<vector<int> > g(n); int m = p.size(); vector<bool> vis(n); for(int i = 0; i < m; ++i) { const int u = p[i]; const int v = q[i]; g[u].push_back(v); g[v].push_back(u); } bool ok = false; for(int i = 0; i < n; ++i) { if(g[i].size() == 1u) { ok = true; res[i] = 1; vis[i] = true; break; } } if(!ok) { res[0] = 1; vis[0] = true; } int startv = 0; while(res[startv]) { startv++; } int quota = b; auto b_dfs = [&](auto&& dfs, int u) -> void { assert(quota >= 0); if(quota == 0) { return; } assert(!vis[u] and !res[u]); vis[u] = true; res[u] = 2; quota--; for(int to : g[u]) { if(!vis[to]) { dfs(dfs, to); assert(quota >= 0); if(quota == 0) { return; } } } }; b_dfs(b_dfs, startv); for(int i = 0; i < n; ++i) { if(!res[i]) { res[i] = 3; } } return res; } /* 6 5 1 3 2 0 1 0 2 0 3 0 4 0 5 */
#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...