| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1021913 | nisanduu | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,char> hash;
map<char,ll> mp;
ll n1,n2;
ll dfs(ll& cr,vector<pair<ll,char>> &v,ll node,vector<vector<ll>>&adj,ll parent){
ll am = 1;
for(auto el:adj[node]){
if(el!=parent){
am += dfs(cr,v,el,adj,node);
if(cr>=2) return 0;
if(am>=v[cr].first){
if(cr==0) n1=el;
else n2=el;
hash[el]=v[cr].second;
return 0;
}
}
}
return am;
}
void dfs2(ll node,vector<vector<ll>>&adj,ll parent,ll cnt,char let,ll target){
if(node==target){
dfs3(node,adj,parent,cnt,let);
return;
}
for(auto el:adj[node]){
if(el!=parent){
dfs2(el,adj,node,cnt,let,target);
}
}
}
void dfs3(ll node,vector<vector<ll>>&adj,ll parent,ll &cnt,char let){
if(cnt==0) return;
if(hash[node] != let) return;
res[node]=mp[let];
cnt--;
for(auto el:adj[node]){
if(el!=parent){
dfs3(el,adj,node,cnt,let);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
ll A=a,B=b,C=c;
vector<int> res(n);
int m = p.size();
vector<vector<int>> adj(n+2);
for(int i=0;i<m;i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<int> vis(n+2);
if(m == n-1){
mp['A']=1;
mp['B']=c;
mp['C']=3;
vector<pair<ll,char>> v;
v.push_back({A,'A'});
v.push_back({B,'B'});
v.push_back({C,'C'});
sort(v.begin(),v.end());
ll parentNode = 0;
ll am = dfs(0,v,parentNode,adj,-1);
if(cr<2&&am>=v[cr].first){
mp[parentNode] = v[cr].second;
}
dfs2(parentNode,adj,-1,v[0].first,v[0].second,n1);
dfs2(parentNode,adj,-1,v[1].first,v[1].second,n2);
for(ll i=0;i<n;i++){
if(res[i]==0){
res[i]=mp[v[2].second];
}
}
return res;
}
bool f1=0;
if(B>C){
swap(B,C);
f1=1;
}
stack<int> ds;
ds.push(0);
vector<int> vis1(n+10);
while(!ds.empty()){
int node = ds.top();
ds.pop();
if(vis1[node]) continue;
vis1[node]=1;
if(B>0){
res[node]=f1 ? 3 : 2;
B--;
}else if(A>0){
A--;
res[node]=1;
}else{
C--;
res[node]=f1 ? 2 : 3;
}
for(auto el:adj[node]){
if(!vis1[el]){
ds.push(el);
}
}
}
assert(A==0&&B==0&&C==0);
return res;
}