Submission #940888

#	Time	Username	Problem	Language	Result	Execution time	Memory
940888		Pacybwoah	Village (BOI20_village)	C++17	50 / 100	107 ms	22368 KiB

Village

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > graph;
vector<int> match,prem;
vector<vector<int> > dp;
void dfs_min(int node,int parent){
    for(auto x:graph[node]){
        if(x==parent) continue;
        dfs_min(x,node);
        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 main(){
    int n;
    cin>>n;
    graph.resize(n+1);
    prem.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;
        }
    }
    cout<<min_cnt<<" 1\n";
    for(int i=1;i<=n;i++) cout<<ans_min[i]<<" \n"[i==n];
    for(int i=1;i<=n;i++) cout<<ans_min[i]<<" \n"[i==n];
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50