Submission #198500

#TimeUsernameProblemLanguageResultExecution timeMemory
198500AkashiSplit the Attractions (IOI19_split)C++14
18 / 100
2266 ms575864 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; const int SZ = 2e5 + 5; vector <int> v[SZ]; int n; int d[SZ], Max[SZ], TT[SZ]; bool viz[SZ]; void dfs(int nod){ viz[nod] = 1; d[nod] = 1; for(auto it : v[nod]){ if(viz[it]) continue ; TT[it] = nod; dfs(it); d[nod] += d[it]; Max[nod] = max(Max[nod], d[it]); } } int find_centroid(int nod){ viz[nod] = 1; if(max(Max[nod], n - d[nod]) <= n / 2) return nod; for(auto it : v[nod]){ if(viz[it]) continue ; int x = find_centroid(it); if(x) return x; } return 0; } vector <int> comp[SZ]; int id[SZ], RG[SZ]; inline int find(int x){ int R = x; while(R != id[R]) R = id[R]; while(id[x] != R){ int aux = id[x]; id[x] = R; x = aux; } return R; } inline void unite(int x, int y){ if(x == y) return ; if(RG[x] >= RG[y]) id[y] = x, RG[x] += RG[y]; else id[x] = y, RG[y] += RG[x]; } void make_comp(int nod, int NR){ comp[NR].push_back(nod); viz[nod] = 1; for(auto it : v[nod]){ if(viz[it]) continue ; unite(find(it), find(nod)); make_comp(it, NR); } } bool merge_comp(int nod, int &am, int a){ viz[nod] = 1; for(auto it : v[nod]){ if(viz[it]) continue ; if(find(it) == find(nod)) merge_comp(nod, am, a); else{ unite(find(nod), find(it)); am = RG[find(nod)]; if(am >= a) break ; merge_comp(nod, am, a); } } return 0; } int cul[SZ]; void paint_comp(int nod, int &rem, int c){ if(rem == 0) return ; viz[nod] = 1; --rem; cul[nod] = c; for(auto it : v[nod]){ if(viz[it] || cul[it] || find(it) != find(nod)) continue ; if(rem) paint_comp(it, rem, c); } } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { n = N; vector<int> res(n); int m = p.size(); for(int i = 0; i < m ; ++i){ v[p[i] + 1].push_back(q[i] + 1); v[q[i] + 1].push_back(p[i] + 1); } int ca = 1, cb = 2, cc = 3; if(a > b) swap(a, b), swap(ca, cb); if(a > c) swap(a, c), swap(ca, cc); if(b > c) swap(b, c), swap(cb, cc); for(int i = 1; i <= n ; ++i) id[i] = i, RG[i] = 1; dfs(1); memset(viz, 0, sizeof(viz)); int nod = find_centroid(1); memset(viz, 0, sizeof(viz)); dfs(nod); memset(viz, 0, sizeof(viz)); int NR = 0; viz[nod] = 1; for(auto it : v[nod]){ make_comp(it, NR); NR++; } bool found = false; int wh = 0; for(int i = 0; i < NR ; ++i){ if(comp[i].size() >= a){ found = true; wh = comp[i][0]; break ; } } //cerr << found << endl; if(!found){ memset(viz, 0, sizeof(viz)); viz[nod] = 1; for(int i = 0; i < NR ; ++i){ int x = comp[i].size(); bool ok = merge_comp(comp[i][0], x, a); if(ok){ wh = comp[i][0]; break ; } } } if(wh == 0) return res; memset(viz, 0, sizeof(viz)); viz[nod] = 1; paint_comp(wh, a, ca); for(int i = 1; i <= n ; ++i) unite(find(i), find(wh)); memset(viz, 0, sizeof(viz)); paint_comp(nod, b, cb); for(int i = 0; i < n ; ++i){ if(cul[i + 1] == 0) cul[i + 1] = cc; res[i] = cul[i + 1]; } return res; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(comp[i].size() >= a){
      ~~~~~~~~~~~~~~~^~~~
#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...