제출 #815037

#제출 시각아이디문제언어결과실행 시간메모리
815037physics07Split the Attractions (IOI19_split)C++17
18 / 100
110 ms23448 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<int> adj[100001], tree[100001]; bool visited[100001]; int sz[100001], n, c, cc[100001]; int dfs_tree(int x) { visited[x]=1; sz[x]=1; for(auto i: adj[x]) if(!visited[i]) { tree[x].push_back(i); tree[i].push_back(x); sz[x]+=dfs_tree(i); } return sz[x]; } int centroid(int x) { visited[x]=1; for(auto i: tree[x]) if(!visited[i] && sz[i]*2>n) return centroid(i); return x; } int sol(int x) { visited[x]=1; cc[x]=1; for(auto i: adj[x]) if(!visited[i] && i!=c) cc[x]+=sol(i); return cc[x]; } vector<int> ans; int cnt; void get_all(int x, int p, int avoid=-1) { visited[x]=1; ans[x]=p; cnt--; if(cnt<=0) return; for(auto i: adj[x]) if(!visited[i] && i!=avoid) { get_all(i, p, avoid); if(cnt<=0) return; } } vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) { n=N; vector<pair<int, int>> v; v.push_back({A, 1}); v.push_back({B, 2}); v.push_back({C, 3}); sort(v.begin(), v.end()); int a=v[0].first, b=v[1].first, c=v[2].first; int color[]={v[0].second, v[1].second, v[2].second}; for(int i=0; i<n; i++) ans.push_back(0); int m=(int)p.size(); for(int i=0; i<m; i++) { adj[p[i]].push_back(q[i]); adj[q[i]].push_back(p[i]); } dfs_tree(0); memset(visited, 0, sizeof(visited)); c=centroid(0); memset(visited, 0, sizeof(visited)); bool flag=0; int idx=0; for(int i=0; i<n; i++) if(!visited[i] && i!=c) { if(sol(i)>=a) { flag=1; idx=i; break; } } if(!flag) return ans; memset(visited, 0, sizeof(visited)); cnt=a; get_all(idx, color[0], c); cnt=b; get_all(c, color[1]); for(int i=0; i<n; i++) if(!ans[i]) ans[i]=color[2]; 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...