Submission #951653

#	Time	Username	Problem	Language	Result	Execution time	Memory
951653		temmieowo	Village (BOI20_village)	C++14	56 / 100	54 ms	13992 KiB

Village

#include <bits/stdc++.h>
#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

const int MAX_N = 100000+10;
const int INF = 2e18;

int n;
int a, b;
vector<vector<int>> G(MAX_N);
bitset<MAX_N> vis;

int total = 0;
int ma = -INF, mi = INF;
vector<int> ma_ans(MAX_N, -1), mi_ans(MAX_N, -1);

pair<int, int> dfs2(int now, int pre){ // <最遠點距離, 最遠點>
    pair<int, int> ret = {0, now};

    for (auto x : G[now]){
        if (x!=pre && vis[x]==0){
            pair<int, int> res = dfs2(x, now);
            ret = max(ret, res);
        }
    }

    ret.first++;
    return ret;
}

void dfs3(int now, int pre){
    // cerr << now << endl;
    for (auto x : G[now]){
        if (x!=pre){
            dfs3(x, now);
        }
    }

    if (mi_ans[now]==-1){
        if (pre!=-1){
            mi_ans[now] = (mi_ans[pre]==-1 ? pre : mi_ans[pre]);
            mi_ans[pre] = now;
        }else{
            mi_ans[now] = mi_ans[G[now].back()];
            mi_ans[G[now].back()] = now;
        }
        total += 2;
    }
    return;
}

void solve2(){

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

    // 找到最長的方式
    if (n<=1000){
        total = 0;
        pair<int, int> aa, bb;
        for (int i=0 ; i<n/2 ; i++){
            for (int j=0 ; j<n ; j++){
                if (vis[j]==0){
                    aa = dfs2(j, -1);
                    bb = dfs2(aa.second, -1);

                    vis[aa.second] = 1;
                    vis[bb.second] = 1;
                    total += (bb.first-1)*2;
                    // cerr << "樹直徑：" << aa.second+1 << " & " << bb.second+1 << " 貢獻：" << (bb.first-1)*2 << endl;
                    ma_ans[aa.second] = bb.second;
                    ma_ans[bb.second] = aa.second;
                    break;
                }
            }
        }
        if (n%2==1){
            for (int i=0 ; i<n ; i++){
                if (ma_ans[i]==-1){
                    ma_ans[i] = ma_ans[aa.second];
                    ma_ans[aa.second] = i;
                }
            }
        }
        ma = total;
    }

    // 找到最短的方法
    total = 0;
    dfs3(0, -1);
    mi = total;

    // output
    cout << mi << " " << (ma*(n<=1000)) << "\n";
    for (int i=0 ; i<n ; i++){
        cout << mi_ans[i]+1 << " ";
    }
    cout << "\n";
    for (int i=0 ; i<n ; i++){
        if (n>1000){
            cout << 1 << " ";
        }else{
            cout << ma_ans[i]+1 << " ";
        }
    }
    cout << "\n";

    return;
}

signed main(){

    fastio;

    int t = 1;
    while (t--){
        solve2();
    }

    return 0;
}

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