제출 #722950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722950		Darren0724	Split the Attractions (IOI19_split)	C++17	0 / 100	468 ms	1048576 KiB

split

#include "split.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
const int N=100005;
vector<int> adj[N],res;
int sz[N],pa[N];
pair<int,int> p={-1,-1};
int n;
int cnt=0;
void get_sz(int k){
    sz[k]=1;
    for(int j:adj[k]){
        if(j==pa[k]){
            continue;
        }
        pa[j]=k;
        get_sz(j);
        sz[k]+=sz[j];
    }
}
int cen(int k,int sz1){
    for(int j:adj[k]){
        if(j==pa[k]){
            continue;
        }
        if(sz[j]*2>=sz1){
            return cen(j,sz1);
        }
    }
    return k;
}
void dfs(int k,int pa,int goal){
    if(sz[k]>=goal){
        p=max(p,{n-sz[k],k});
    }
    for(int j:adj[k]){
        if(j==pa){
            continue;
        }
        dfs(j,k,goal);
    }
}
void draw(int k,int pa,bool yes,int root,int goal,int num){
    if(k==root){
        yes=1;
    }
    if(cnt==goal){
        return;
    }
    if(yes){
        cnt++;
        res[k]=num;
    }
    for(int j:adj[k]){
        if(j==pa){
            continue;
        }
        draw(j,k,yes,root,goal,num);
    }
}
vector<int> find_split(int n1, int a, int b, int c, vector<int> x, vector<int> y) {
    vector<int> ans1={0,1,2,3};
    if(a>b){
        swap(a,b);
        swap(ans1[1],ans1[2]);
    }
    if(a>c){
        swap(a,c);
        swap(ans1[1],ans1[3]);
    }
    if(b>c){
        swap(b,c);
        swap(ans1[2],ans1[3]);
    }
    ans1[0]=ans1[3];
    n=n1;
	res.resize(n);
    int m=x.size();
    for(int i=0;i<m;i++){
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    get_sz(0);
    int c1=cen(0,n);
    get_sz(c1);
    dfs(c1,c1,a);
    if(p.first<b){
        return res;
    }
    draw(c1,c1,0,p.second,a,1);
    cnt=0;

    draw(pa[p.second],p.second,0,pa[p.second],b,2);
    for(int i=0;i<n;i++){
        res[i]=ans1[res[i]];
    }

	return res;
}
/*
7 6 4 2 1
0 1
0 2
1 3
1 4
2 5
2 6
*/
/*
10 9 2 7 1
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36