제출 #253714

#제출 시각아이디문제언어결과실행 시간메모리
253714ErkhemkhuuSplit the Attractions (IOI19_split)C++17
0 / 100
2 ms2688 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define F first #define S second const ll N = 100005; vector <int> path, path1; bool vis[N]; vector <vector <int> > adj(N); int need1, need2; void dfs(int v, int cur) { path.pb(v); if(cur == need1 + 1) return; vis[v] = true; for(auto &u: adj[v]) { if(vis[u]) continue; dfs(u, cur + 1); } return; } void dfs1(int v, int cur) { path1.pb(v); if(cur == need2 + 1) return; vis[v] = true; for(auto &u: adj[v]) { if(vis[u]) continue; dfs1(u, cur + 1); } return; } vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) { int m = p.size(), i; for(i = 0; i < m; i++) { adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } vector <int> vc; vc = {a, b, c}; sort(vc.begin(), vc.end()); need1 = vc[0]; need2 = vc[1]; dfs(0, 1); for(i = n - 1; i >= 1; i--) { if(!vis[i]) { dfs1(i, 1); break; } } vector <int> ans(n, 0); for(auto &x: path) ans[x] = 1; for(auto &x: path1) ans[x] = 2; for(i = 0; i < n; i++) if(!vis[i]) ans[i] = 3; 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...