Submission #834252

#	Time	Username	Problem	Language	Result	Execution time	Memory
834252		jasmin	Village (BOI20_village)	C++17	75 / 100	65 ms	23460 KiB

Village

//BOI 2020
#include<bits/stdc++.h>
using namespace std;

int dfsbig(int v, int p, vector<vector<int> >& adi, vector<int>& pre, int n, int& ans){
    pre.push_back(v);

    int s=1;
    for(auto u: adi[v]){
        if(u==p) continue;

        s+=dfsbig(u, v, adi, pre, n, ans);
    }

    ans += 2*min(s, n-s);
    return s;
}

bool dfssmall(int v, int p, vector<vector<int> >& adi, vector<int>& go, int& ans, int n){

    vector<int> unmatched;
    for(auto u: adi[v]){
        if(u==p) continue;

        if(dfssmall(u, v, adi, go, ans, n)){
            unmatched.push_back(u);
        }
    }

    if(unmatched.empty()){
        ans+=2;
        return true;
    }

    unmatched.push_back(v);
    int s=unmatched.size();
    for(int i=0; i<s; i++){
        go[unmatched[i]] = unmatched[(i+1)%s];
    }
    return false;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int> > adi(n);
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adi[a].push_back(b);
        adi[b].push_back(a);
    }

    int leaf=-1;
    for(int i=0; i<n; i++){
        if(adi[i].size()==1) leaf=i;
    }
    int smallest=0;
    vector<int> gosmall(n);
    dfssmall(adi[leaf][0], -1, adi, gosmall, smallest, n);

    vector<int> pre;
    int biggest=0;
    dfsbig(0, -1, adi, pre, n, biggest);

    vector<int> gobig(n);
    for(int i=0; i<n; i++){

        gobig[pre[i]] = pre[(i+n/2)%n];
    }

    cout << smallest << " " << biggest << "\n";
    for(int i=0; i<n; i++){
        cout << gosmall[i]+1 << " ";
    }
    cout << "\n";
    for(int i=0; i<n; i++){
        cout << gobig[i]+1 << " ";
    }
    cout << "\n";
}

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