Submission #1256239

#TimeUsernameProblemLanguageResultExecution timeMemory
1256239nerrrminSplit the Attractions (IOI19_split)C++20
0 / 100
59 ms14532 KiB
#include "split.h" #define pb push_back #include<bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10; int m, deg[maxn]; vector < int > g[maxn]; int used[maxn]; vector < int > path; int sub[maxn], par[maxn]; void dfs(int beg, int from) { used[beg] = 1; sub[beg] = 1; path.pb(beg); for (auto nb: g[beg]) { if(used[nb])continue; dfs(nb, beg); sub[beg] += sub[nb]; } } int c1, c2, c3; int col1, col2, col3; int track[maxn]; void rec(int beg, int from) { if(!c1)return; c1 --; track[beg] = col1; for (auto nb: g[beg]) { if(nb == from)continue; if(track[nb])continue; rec(nb, beg); } } void rec2(int beg, int from) { if(!c2)return; c2 --; track[beg] = col2; for (auto nb: g[beg]) { if(nb == from)continue; if(track[nb])continue; rec2(nb, beg); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { m = p.size(); for (int i = 0; i < m; ++ i) { g[p[i]].pb(q[i]); g[q[i]].pb(p[i]); } if(a <= min(b, c)) { c1 = a; col1 = 1; } if(b <= min(a, c)) { c1 = b; col1 = 2; } if(c <= min(a, b)) { c1 = c; col1 = 3; } if(a >= max(b, c)) { c3 = a; col3 = 1; } if(b >= max(a, c)) { c3 = b; col3 = 2; } if(c >= max(a, c)) { c3 = c; col3 = 3; } col2 = 6 - col1 - col3; c2 = n - c1 - c3; assert(col1 >= 1 && col1 <= 3); assert(col2 >= 1 && col2 <= 3); assert(col3 >= 1 && col3 <= 3); dfs(0, -1); vector < int > ans; for (int i = 0; i < n; ++ i) { if(sub[i] >= c1) { rec(i, p[i]); rec2(p[i], -1); for (int j = 0; j < n; ++ j) if(track[j] == 0)track[j] = col3; for (int j = 0; j < n; ++ j) ans.pb(track[j]); return ans; } } for (int i = 0; i < n; ++ i) ans.pb(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...