Submission #1270577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270577		enzy	Village (BOI20_village)	C++20	50 / 100	54 ms	20156 KiB

Village

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(args...) fprintf(stderr,args)
const int maxn=1e5+10;
const int inf=1e9+7;
vector<int>v[maxn], aux;
int val[maxn], resp1, qm1[maxn], pai[maxn], sub[maxn], prof[maxn], qm2[maxn], n, resp2;
void dfs(int u){
    if(pai[u]!=u) aux.push_back(u);
    sub[u]=1;
    for(int viz : v[u]){
        if(viz==pai[u]) continue;
        pai[viz]=u;
        prof[viz]=prof[u]+1;
        dfs(viz);
        sub[u]+=sub[viz];
        if(val[viz]==viz){
            swap(val[viz],val[u]);
            resp1+=2;
        }
    }
}
int centroide(int u){
    for(int viz : v[u]) if(sub[viz]>(n/2)&&viz!=pai[u]) return centroide(viz);
    return u;
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i=1;i<=n;i++) val[i]=i;
    for(int i=1;i<n;i++){
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    pai[1]=1;
    dfs(1);
    int c=centroide(1);
    pai[c]=c; prof[c]=0;
    aux.clear();
    dfs(c);
    int tam=aux.size(), half=tam/2;
    for(int i=1;i<=n;i++) resp2+=2*prof[i];
    if(n%2){
        qm2[aux[0]]=c;
        qm2[c]=aux[half];
        qm2[aux[half]]=aux[0];
    }else{
        qm2[c]=aux.back();
        qm2[aux.back()]=c;
        aux.pop_back();
        if(!aux.empty()){
            qm2[aux[0]]=aux[half];
            qm2[aux[half]]=aux[0];    
        }
    }
    for(int i=1;i<half;i++){
        qm2[aux[i]]=aux[i+half];
        qm2[aux[i+half]]=aux[i];
    }
    if(val[1]==1){
        resp1+=2;
        swap(val[1],val[v[1][0]]);
    }
    for(int i=1;i<=n;i++) qm1[val[i]]=i;
    cout << resp1 << " " << resp2 << endl;
    for(int i=1;i<=n;i++) cout << qm1[i] << " ";
    cout << endl;
    for(int i=1;i<=n;i++) cout << qm2[i] << " ";
    cout << endl;
}

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