| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 406291 | ngrace | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> adj;
vector<bool> vis;
int dfs(int cur){//on tree
if(vis[cur]){
return 0;
}
vis[cur]=true;
int ret=0;
for(pair<int,int>& it:adj[cur]){
int sub=dfs(it.first);
ret+=sub;
it.second=sub;
}
return ret+1;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
if(a==1){//sub 2
vector<int> answer(n,3);
vector<vector<int>> lineAdj(n);
for(int i=0;i<p.size();i++){
lineAdj[p[i]].push_back(q[i]);
lineAdj[q[i]].push_back(p[i]);
}
stack<int> s;
s.push(0);
vector<bool> vis(n);
while(s.size()>0 && b>0){
int cur=s.top();
s.pop();
if(!vis[cur]){
vis[cur]=true;
answer[cur]=2;
b--;
for(int& it:adj[cur]){
s.push(it);
}
}
}
for(int i=0;i<n;i++){
if(answer[i]==3){
answer[i]=1;
break;
}
}
return answer;
}
else if(false){//line case
vector<vector<int>> lineAdj(n);
for(int i=0;i<p.size();i++){
lineAdj[p[i]].push_back(q[i]);
lineAdj[q[i]].push_back(p[i]);
}
int root=0;
for(int i=0;i<p.size();i++){
if(lineAdj[i].size()==1){
root=i;
break;
}
}
vector<int> par(n);
par[root]=root;
int next=lineAdj[root][0];
int last=root;
for(int i=1;i<n;i++){
par[last]=next;
if(i==n-1){
break;
}
if(lineAdj[next][0]!=last){
last=next;
next=lineAdj[next][0];
}
else{
last=next;
next=lineAdj[next][1];
}
}
vector<int> answer(n);
int cur=root;
for(int i=0;i<n;i++){
if(a>0){
a--;
answer[cur]=1;
}
else if(b>0){
b--;
answer[cur]=2;
}
else{
answer[cur]=3;
}
cur=par[cur];
}
return answer;
}
else if(p.size()==n-1){//tree case
adj=vector<vector<pair<int,int>>>(n);
for(int i=0;i<p.size();i++){
adj[p[i]].push_back({q[i],-1});
adj[q[i]].push_back({p[i],-1});
}
vis=vector<bool>(n);
dfs(0);
vector<int> answer(n,0);
bool done=false;
for(int i=0;i<p.size();i++){
for(pair<int,int> it:adj[i]){
int prim=-1,sec=-1,spare=-1;
if(it.second>=a){
if(n-it.second>=b){
prim=1;
sec=2;
spare=3;
done=true;
}
else if(n-it.second>=c){
prim=1;
sec=3;
spare=2;
done=true;
}
}
if(it.second>=b && !done){
if(n-it.second>=a){
prim=2;
sec=1;
spare=3;
done=true;
}
else if(n-it.second>=c){
prim=2;
sec=3;
spare=1;
done=true;
}
}
if(it.second>=c && !done){
if(n-it.second>=a){
prim=3;
sec=1;
spare=2;
done=true;
}
else if(n-it.second>=b){
prim=3;
sec=2;
spare=1;
done=true;
}
}
if(prim!=-1){
done=true;
int primC=(prim==1)?a:((prim==2)?b:c);
int secC=(sec==1)?a:((sec==2)?b:c);
vis=vector<bool>(n,false);
stack<int> s;
vis[i]=true;
s.push(it.first);
while(s.size()>0){
int cur=s.top();
s.pop();
if(!vis[cur]){
vis[cur]=true;
if(primC>0){
primC--;
answer[cur]=prim;
}
else{
answer[cur]=spare;
}
for(pair<int,int> pt:adj[cur]){
s.push(pt.first);
}
}
}
vis=vector<bool>(n,false);
vis[it.first]=true;
s.push(i);
while(s.size()>0){
int cur=s.top();
s.pop();
if(!vis[cur]){
vis[cur]=true;
if(secC>0){
secC--;
answer[cur]=sec;
}
else{
answer[cur]=spare;
}
for(pair<int,int> pt:adj[cur]){
s.push(pt.first);
}
}
}
}
if(done){
break;
}
}
if(done){
break;
}
}
return answer;
}
}