| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 591057 | almothana05 | 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>
#define mod 1000000007
using namespace std;
vector<pair<int , int> >gru;
vector<int> vis;
vector<int>gr[300000];
int re , pl , maxi = mod , f[300000];
int dfs(int x){
int sub = 1;
vis[x] = 1;
for(int i = 0 ; i< gr[x].size() ; i ++){
int kind = gr[x][i];
if(vis[kind] == 0){
sub += dfs(kind);
}
else{
f[x] = kind;
}
}
if(sub == gru[0].first + gru[1].first + gru[2].first ){
return 0;
}
if(sub >= gru[0].first && sub < maxi){
maxi = sub;
pl = x;
}
return sub;
}
void dfs1(int x , int ins){
if(re <= 0){
return;
}
vis[x] = ins;
re--;
for(int i = 0 ; i < gr[x].size() ; i++){
int kind = gr[x][i];
if(kind != f[x] && vis[kind] == 0){
dfs1(kind , ins);
}
}
}
vector<int> find_split(int menge, int a, int b, int c, vector<int> p, vector<int> q) {
int root;
for(int i = 0 ;i < menge ; i++){
vis.push_back(0);
}
gru.push_back({a , 1});
gru.push_back({b , 2});
gru.push_back({c , 3});
sort(gru.begin() , gru.end());
for(int i = 0 ; i < p.size() ; i++){
gr[p[i]].push_back(q[i]);
gr[q[i]].push_back(p[i]);
}
for(int i = 0 ; i < menge ; i++){
if(gr[i].size() > 1){
root = i;
break;
}
}
dfs(root);
for(int i = 0 ; i < menge ; i++){
vis[i] = 0;
}
if(maxi == mod){
return vis;
}
re = gru[0].first;
dfs1( pl , gru[0].second );
re = gru[1].first;
dfs1(root , gru[1].second);
for(int i = 0 ; i < menge ; i ++){
if(vis[i] == 0){
vis[i] = gru[2].second;
}
}
return vis;
}