| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1047988 | NotLinux | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
const int inf = 1e9 + 7;
const int LIM1 = 1e5 + 7;
int subt[LIM1] , N , A , B , C , vis[LIM1] , past[LIM1];
vector < int > graph[LIM1] , color , tree[LIM1];
int root = -1;
pair < int , int > pai;
void dfs(int node , int par){
subt[node] = 1;
past[node] = par;
tree[par].push_back(node);
for(auto itr : graph[node]){
if(subt[itr] == -1){
dfs(itr , node);
subt[node] += subt[itr];
}
}
// cout << node << " : " << subt[node] << " , " << par << endl;
// if(node == 4)cout << "wtf : " << subt[node] << " >= " << C << " , " << N - subt[node] << " >= " << B << endl;
if(subt[node] >= A and (N - subt[node]) >= B)pai = {1 , 2} , root = node;
if(subt[node] >= B and (N - subt[node]) >= A)pai = {2 , 1} , root = node;
if(subt[node] >= A and (N - subt[node]) >= C)pai = {1 , 3} , root = node;
if(subt[node] >= C and (N - subt[node]) >= A)pai = {3 , 1} , root = node;
if(subt[node] >= B and (N - subt[node]) >= C)pai = {2 , 3} , root = node;
if(subt[node] >= C and (N - subt[node]) >= B)pai = {3 , 2} , root = node;
}
int sayac;
void dfs1(int node , int paint){
if(sayac == 0)return;
color[node] = paint;
vis[node] = 1;
sayac--;
// cout << "Dfs : " << node << " , " << paint << " , " << past[node] << endl;
for(auto itr : tree[node]){
if(vis[itr] == 0 and itr != past[node]){
// cout << node << "->" << itr << endl;
dfs1(itr , paint);
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
N = n , A = a , B = b , C = c;
memset(subt , -1 , sizeof(subt));
for(int i = 0;i<sz(p);i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
dfs(0 , -1);
// cout << "root : "<< root << endl;
// cout << "lower : " << pai.first << endl;
// cout << "upper : " << pai.second << endl;
if(root == -1){
color.assign(N , 0);
}
else{
int q[3] = {A , B , C};
set < int > ste = {1 , 2 , 3};
ste.extract(pai.first);
ste.extract(pai.second);
color.assign(N , *ste.begin());
// cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
sayac = q[pai.first - 1];
dfs1(root , pai.first);
// cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
sayac = q[pai.second - 1];
dfs1(0 , pai.second);
// cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
}
return color;
}
int main() {
int n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
vector<int> p(m), q(m);
for (int i=0; i<m; i++)
cin >> p[i] >> q[i];
vector<int> result = find_split(n, a, b, c, p, q);
for (int i=0; i<(int)result.size(); i++)
cout << result[i] << " ";
cout << endl;
}