Submission #1291144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291144		Ludissey	Village (BOI20_village)	C++20	50 / 100	72 ms	28024 KiB

Village

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;

vector<vector<int>> neigh;

vector<int> sz;
vector<int> v_mn_ans;
vector<int> v_mx_ans;
vector<vector<int>> ch;
int n; 
int mn_ans=0;
int mx_ans=0;
int find_mn(int x, int p){
    sz[x]=1;
    vector<int> v;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        int fm=find_mn(u,x);
        sz[x]+=sz[u];
        if(fm!=-1) v.push_back(fm);
    }
    v.push_back(x);
    if(sz(v)==1) return v[0];
    for (int i = 0; i < sz(v); i++)
    {
        v_mn_ans[v[i]]=v[(int)((i+1)%(int)sz(v))];
        mn_ans+=2-(v[i]==x||v[(i+1)%sz(v)]==x);
    }
    return -1;
}

void find_mx(int x, int p, int d, int indx){
    ch[indx].push_back(x);
    mx_ans+=d*2;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        find_mx(u,x,d+1,indx);
    }
}


int find_centroid(int x, int p){
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        if(sz[u]>n/2) return find_centroid(u,x);
    }
    return x;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    neigh.resize(n);
    sz.resize(n,1);
    v_mn_ans.resize(n,-1);
    v_mx_ans.resize(n,-1);
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        neigh[a-1].push_back(b-1);
        neigh[b-1].push_back(a-1);
    }
    int rt=0;
    for (int i = 0; i < n; i++) { if(sz(neigh[i])==1) rt=neigh[i][0]; }
    
    find_mn(rt,rt);
    int centr=find_centroid(rt,rt);
    ch.resize(sz(neigh[centr]));
    for (int i = 0; i < sz(neigh[centr]); i++)
    {
        find_mx(neigh[centr][i],centr,1,i);    
    }
    sort(all(ch),[](vector<int> a, vector<int> b){ 
        if(sz(a)>sz(b)) return true;
        return false;
    });
    int l=0;
    int r=sz(ch)-1;
    int li=0;
    int ri=sz(ch[r])-1;
    int t=0;
    while(l<r||(l==r&&li<ri)){
        if(ri==-1) { r--, ri=sz(ch[r])-1; continue; }
        if(li==sz(ch[l])) { li=0, l++; continue; }
        if(t%2==0){
                v_mx_ans[ch[l][li]]=ch[r][ri];
            li++;
        }else{
            v_mx_ans[ch[r][ri]]=ch[l][li];
            ri--;
        }
        t++;
    }
    if(t%2==0){
        v_mx_ans[ch[l][li]]=centr;
        v_mx_ans[centr]=ch[0][0];
    }else{
        v_mx_ans[ch[r][ri]]=centr;
        v_mx_ans[centr]=ch[0][0];
    }
    //mx_ans--;
    cout << mn_ans << " " << mx_ans << "\n";
    for (int i = 0; i < n; i++) cout << v_mn_ans[i]+1 << " ";
    cout << "\n";
    for (int i = 0; i < n; i++) cout << v_mx_ans[i]+1 << " ";
    return 0;
}                           

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