제출 #614082

#제출 시각아이디문제언어결과실행 시간메모리
6140822fat2codeSplit the Attractions (IOI19_split)C++17
0 / 100
75 ms14208 KiB
#include <bits/stdc++.h> #define fr first #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define sc second #define all(s) s.begin(), s.end() //#define int long long #define rc(s) return cout << s, 0 using namespace std; const int nmax = 100005; int N, M, A, B, C, sz[nmax], centroid, indx1, indx2, indx3; vector<int> res, nod[nmax], nod_MST[nmax]; bitset<nmax>viz; void dfs(int s){ viz[s] = 1; sz[s] = 1; for(auto it : nod[s]){ if(!viz[it]){ nod_MST[s].push_back(it); nod_MST[it].push_back(s); dfs(it); sz[s] += sz[it]; } } } void dfs2(int s){ viz[s] = 1; sz[s] = 1; for(auto it : nod_MST[s]){ if(!viz[it]){ dfs2(it); sz[s] += sz[it]; } } } int findcentroid(int s, int par = 0){ for(auto it : nod_MST[s]){ if(it != par && sz[it] > (N / 2)){ return findcentroid(it, s); } } return s; } void dfs_vanilla(int s, int par, int cock){ if(A == 0) return; else{ res[s - 1] = cock; A--; for(auto it : nod_MST[s]){ if(it != par && !res[it]) dfs_vanilla(it, s, cock); } } } void construct(int it){ dfs_vanilla(it, centroid, indx1); A = B; dfs_vanilla(centroid, 0, indx2); for(int i=0;i<N;i++){ if(!res[i]){ res[i] = indx3; } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { N = n; M = p.size(); vector<pair<int,int>>tz; tz.push_back({a, 1}); tz.push_back({b, 2}); tz.push_back({c, 3}); sort(all(tz)); A = tz[0].fr; B = tz[1].fr; C = tz[2].fr; indx1 = tz[0].sc, indx2 = tz[1].sc, indx3 = tz[2].sc; res.resize(N); for(int i=0;i<M;i++){ nod[p[i]].push_back(q[i]); nod[q[i]].push_back(p[i]); } dfs(1); centroid = findcentroid(1); viz.reset(); for(int i=1;i<=n;i++) sz[i] = 0; dfs2(centroid); for(auto it : nod_MST[centroid]){ if(sz[it] >= A){ construct(it); return res; } } 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...