| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 591106 | 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 <cstdio>
#include <cassert>
using namespace std;
#include "split.h"
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
vector<pair<int , int> >gru;
vector<int> vis;
vector<int>gr[500000];
int re , pl = -1 , maxi = mod , f[500000] ,pl2 , menge;
int unt[300000] , ob[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;
}
}
unt[x] = sub;
ob[x] = menge - unt[x] + 1;
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(vis[kind] == 0){
dfs1(kind , ins);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int root;
menge = n;
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 x = 0 ; x < menge ; x++){
vis[x] = 0;
for(int i = 0 ; i < gr[x].size() ; i++ ){
int kind = gr[x][i];
if(kind == f[x]){
if(unt[x] > gru[0].first && maxi > unt[x]){
maxi = unt[x];
pl = x;
pl2 = kind;
}
}
else{
if(menge - unt[kind] > gru[0].first && maxi > menge - unt[kind]){
maxi = menge - unt[kind];
pl = x;
pl2 = kind;
}
}
}
}
if(maxi == mod){
return vis;
}
vis[pl] = gru[0].second;
re = gru[1].first;
dfs1( pl2 , gru[1].second );
if(re > 0){
// assert(gru[2].first >= gru[1].first && gru[1].first > gru[0].first);
for(int i = 0 ; i < menge ; i++){
vis[i] =0;
}
return vis;
}
re = gru[0].first;
dfs1(pl , gru[0].second);
for(int i = 0 ; i < menge ; i ++){
if(vis[i] == 0){
vis[i] = gru[2].second;
}
}
return vis;
}
int main() {
int n, m, a, b, c;
assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
vector<int> p(m), q(m);
for (int i=0; i<m; i++)
assert(2 == scanf("%d%d", &p[i], &q[i]));
fclose(stdin);
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++)
printf("%s%d", ((i>0)?" ":""), result[i]);
printf("\n");
fclose(stdout);
return 0;
}