이 제출은 이전 버전의 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;
int root = -1;
pair < int , int > pai;
random_device rd;
mt19937 rng(rd());
// shuffle(v.begin() , v.end() , rng);
int rand(int l, int r) {
return rng() % (r - l + 1) + l;
}
void dfs(int node , int par){
// cout << "bruh0" << endl;
subt[node] = 1;
// cout << "bruh0.1" << endl;
past[node] = par;
// cout << "bruh0.2" << endl;
// cout << "bruh0.3" << endl;
shuffle(all(graph[node]) , rng);
// cout << "bruh1" << endl;
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 : graph[node]){
if(vis[itr] == 0 and itr != past[node] and past[itr] == node){
// cout << node << "->" << itr << endl;
dfs1(itr , paint);
}
}
}
void solve(){
root = -1;
// cout << "flag-0"<<endl;
memset(vis , 0 , sizeof(vis));
memset(subt , -1 , sizeof(subt));
// cout << "flag-1"<<endl;
int real_root = rand(0 , N-1);
dfs(real_root , -1);
// cout << "flag-2"<<endl;
// cout << "root : "<< root << endl;
// cout << "lower : " << pai.first << endl;
// cout << "upper : " << pai.second << endl;
if(root != -1){
int q[3] = {A , B , C};
set < int > ste = {1 , 2 , 3};
ste.erase(ste.find(pai.first));
ste.erase(ste.find(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(real_root , pai.second);
// cout << "color : ";for(auto itr : color)cout << itr << " ";cout << endl;
}
}
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;
for(int i = 0;i<sz(p);i++){
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
}
const int BRUH = 1000;
color.assign(N , 0);
// cout << "flag0" << endl;
for(int i = 0;i<BRUH;i++){
// cout << "flag0.1" << endl;
solve();
if(color[0] != 0)break;
}
// cout << "flag1" << endl;
return color;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |