Submission #941074

#	Time	Username	Problem	Language	Result	Execution time	Memory
941074		Pacybwoah	Village (BOI20_village)	C++17	100 / 100	114 ms	22400 KiB

Village

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int> > graph;
vector<int> match,prem;
vector<vector<int> > dp;
vector<int> sz,ord;
int n;
typedef long long ll;
ll max_cnt=0;
void dfs_min(int node,int parent){
    sz[node]++;
    for(auto x:graph[node]){
        if(x==parent) continue;
        dfs_min(x,node);
        sz[node]+=sz[x];
        dp[node][0]+=max(dp[x][0],dp[x][1]);
    }
    for(auto x:graph[node]){
        if(x==parent) continue;
        if(dp[node][1]<dp[node][0]-max(dp[x][0],dp[x][1])+dp[x][0]+1){
            dp[node][1]=dp[node][0]-max(dp[x][0],dp[x][1])+dp[x][0]+1;
            prem[node]=x;
        }
    }
}
void dfs_match(int node,int parent,bool flag){
    if(flag||dp[node][0]>=dp[node][1]){
        for(auto x:graph[node]){
            if(x==parent) continue;
            dfs_match(x,node,0);
        }
    }
    else{
        match[node]=prem[node];
        match[prem[node]]=node;
        for(auto x:graph[node]){
            if(x==parent) continue;
            if(x==prem[node]) dfs_match(x,node,1);
            else dfs_match(x,node,0);
        }
    }
}
int dfs_cent(int node,int parent){
    for(auto x:graph[node]){
        if(x==parent) continue;
        if(sz[x]>n/2) return dfs_cent(x,node);
    }
    return node;
}
void dfs_sz(int node,int parent){
    sz[node]=1;
    for(auto x:graph[node]){
        if(x==parent) continue;
        dfs_sz(x,node);
        sz[node]+=sz[x];
    }
    if(parent!=0) max_cnt+=2*min(1ll*sz[node],1ll*(n-sz[node]));
}
void dfs_ord(int node,int parent){
    if(parent!=0) ord.push_back(node);
    for(auto x:graph[node]){
        if(x==parent) continue;
        dfs_ord(x,node);
    }
}
int main(){
    cin>>n;
    graph.resize(n+1);
    prem.resize(n+1);
    sz.resize(n+1);
    int a,b;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dp.resize(n+1,vector<int>(2));
    match.resize(n+1,-1);
    dfs_min(1,0);
    dfs_match(1,0,0);
    vector<int> ans_min(n+1);
    for(int i=1;i<=n;i++){
        if(match[i]!=-1){
            ans_min[i]=match[i];
        }
        else ans_min[i]=i;
    }
    int min_cnt=max(dp[1][1],dp[1][0])*2;
    for(int i=1;i<=n;i++){
        if(match[i]==-1){
            swap(ans_min[i],ans_min[graph[i][0]]),min_cnt+=2;
        }
    }
    int cent=dfs_cent(1,0);
    dfs_sz(cent,0);
    sort(graph[cent].begin(),graph[cent].end(),[&](int a,int b){return sz[a]>sz[b];});
    dfs_ord(cent,0);
    vector<int> ans_max(n+1);
    for(int i=1;i<=n;i++) ans_max[i]=i;
    if(n&1){
        for(int i=0;i<n/2;i++) swap(ans_max[ord[i]],ans_max[ord[i+n/2]]);
        swap(ans_max[cent],ans_max[(cent==1)?2:1]);
    }
    else{
        ord.push_back(cent);
        for(int i=0;i<n/2;i++) swap(ans_max[ord[i]],ans_max[ord[i+n/2]]);
    }
    cout<<min_cnt<<" "<<max_cnt<<"\n";
    for(int i=1;i<=n;i++) cout<<ans_min[i]<<" \n"[i==n];
    for(int i=1;i<=n;i++) cout<<ans_max[i]<<" \n"[i==n];
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50