Submission #784291

#TimeUsernameProblemLanguageResultExecution timeMemory
784291Magikarp4000Split the Attractions (IOI19_split)C++17
0 / 100
867 ms1048576 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define in(v,x) (v.find(x) != v.end()) #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; const int MAXN = 1e5+5; int n,m,a,b,c; vector<int> v[MAXN], res; int p[MAXN], sz[MAXN], cnt; void dfs(int s, int pa) { sz[s] = 1; FORX(u,v[s]) { if (u == pa) continue; dfs(u,s); p[u] = s; sz[s] += sz[u]; } } void dfs1(int s, int pa, int ub, int idx) { if (cnt < ub) { res[s] = idx; cnt++; } FORX(u,v[s]) if (u != pa) dfs1(u,s,ub,idx); } vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) { n = N, a = A, b = B, c = C, m = P.size(); res.resize(n,0); PII h[3] = {{A,1}, {B,2}, {C,3}}; sort(h,h+3); vector<int> noob(n,0); FOR(i,0,m) { v[P[i]].PB(Q[i]); v[Q[i]].PB(P[i]); } p[0] = -1; dfs(0,-1); int mi = INF, x = -1; FOR(i,0,n) { if (sz[i] >= h[0].F && sz[i] < mi) { mi = sz[i]; x = i; } } if (x == -1 || p[x] == -1) return noob; dfs1(x,p[x],h[0].F,h[0].S); cnt = 0; dfs1(p[x],x,h[1].F,h[1].S); if (cnt != h[1].F) return noob; FOR(i,0,n) if (!res[i]) res[i] = h[2].S; 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...