Submission #428354

#TimeUsernameProblemLanguageResultExecution timeMemory
428354HazemSplit the Attractions (IOI19_split)C++14
22 / 100
526 ms1048580 KiB
#include "split.h" #include <bits/stdc++.h> #define LL long long #define F first #define S second using namespace std; const int N = 2e5+10; const LL INF = 1e9; vector<int>adj[N],ans; int n,m,sizes[N],vis[N],par[N],a,b,c,mn = INF; pair<int,pair<int,int>>p1; vector<pair<int,int>>vec; void dfs(int i,int pre){ sizes[i] = 1;par[i] = pre; for(auto x:adj[i]) if(x!=pre) dfs(x,i),sizes[i] += sizes[x]; if(sizes[i]>=a&&sizes[i]-a<mn) mn = sizes[i]-a,p1 = make_pair(i,make_pair(a,1)); if(sizes[i]>=b&&sizes[i]-b<mn) mn = sizes[i]-b,p1 = make_pair(i,make_pair(b,2)); if(sizes[i]>=c&&sizes[i]-c<mn) mn = sizes[i]-c,p1 = make_pair(i,make_pair(c,3)); } void color(int i,int c,int &cnt){ if(vis[i]||!cnt) return ; vis[i] = 1,ans[i] = c; cnt--; for(auto x:adj[i]) color(x,c,cnt); } int cnt[4]; void f(){ dfs(0,n); vis[par[p1.F]] = 1; color(p1.F,p1.S.S,p1.S.F); vis[par[p1.F]] = 0; for(int i=0;i<3;i++) if(p1.S.S!=vec[i].S){ color(0,vec[i].S,vec[i].F); break; } for(int i=0;i<n;i++) cnt[ans[i]]++; int col = 0; for(int i=1;i<4;i++) if(!cnt[i])col = i; for(int i=0;i<n;i++) if(!ans[i])ans[i] = col,cnt[col]++; if(cnt[1]!=a||cnt[2]!=b||cnt[3]!=c) ans = vector<int>(n,0); } vector<int> find_split(int n1, int a1, int b1, int c1, vector<int> p, vector<int> q) { n = n1; m = p.size(); a = a1; b = b1; c = c1; ans = vector<int>(n,0); vec.push_back({a,1}); vec.push_back({b,2}); vec.push_back({c,3}); sort(vec.begin(),vec.end()); for(int i=0;i<m;i++){ adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } f(); 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...