Submission #657337

#	Time	Username	Problem	Language	Result	Execution time	Memory
657337		esomer	Village (BOI20_village)	C++17	100 / 100	199 ms	41276 KiB

Village

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;

struct LCA{
    vector<vector<int>> dp;
    vector<int> depths;
    void DFS(int x, vector<vector<int>>& adj, int p){
        dp[x][0] = p;
        for(auto node : adj[x]){
            if(node != p){
                depths[node] = depths[x] + 1;
                DFS(node, adj, x);
            }
        }
    }
    void build(vector<vector<int>>& adj){
        int n = adj.size();
        dp.assign(n, vector<int>(20, 0)); depths.resize(n);
        depths[0] = 0;
        DFS(0, adj, -1);
        for(int i = 1; i < 20; i++){
            for(int j = 0; j < n; j++){
                if(dp[j][i - 1] == -1) {dp[j][i] = -1; continue;}
                dp[j][i] = dp[dp[j][i - 1]][i - 1];
            }
        }
    }

    int kth(int x, int d){
        for(int k = 19; k >= 0; k--){
            if((1 << k) <= d){
                x = dp[x][k];
                d -= (1 << k);
            }
        }
        return x;
    }

    int lca(int a, int b){
        if(depths[b] > depths[a]) b = kth(b, depths[b] - depths[a]);
        else if(depths[a] > depths[b]) a = kth(a, depths[a] - depths[b]);
        if(a == b) return a;
        int anc = -1;
        for(int k = 19; k >= 0; k--){
            if(dp[a][k] == dp[b][k]){
                anc = max(0, dp[a][k]);
            }else{
                a = dp[a][k];
                b = dp[b][k];
            }
        }
        return anc;
    }

    int dist(int a, int b){
        return depths[a] + depths[b] - 2 * depths[lca(a, b)];
    }
};

struct maximum{
    int centr = -1;

int find_centroid(int x, vector<vector<int>>& adj, int p){
    if(centr != -1) return -1;
    int n = adj.size();
    int subtree = 1;
    bool good = 1;
    for(int node : adj[x]){
        if(node == p) continue;
        int sub = find_centroid(node, adj, x);
        if(centr != -1) return -1;
        subtree += sub;
        if(sub > n / 2) good = 0;
    }
    if(good == 1 && n - subtree <= n / 2){
        centr = x;
        return -1;
    }else return subtree;
}

void DFS(int x, vector<vector<int>>& adj, vector<int>& euler, int p){
    euler.push_back(x);
    for(int node : adj[x]){
        if(node == p) continue;
        DFS(node, adj, euler, x);
    }
}

pair<ll, vector<int>> solve(vector<vector<int>> adj){
    int n = adj.size();
    find_centroid(0, adj, -1);
    vector<int> euler;
    DFS(centr, adj, euler, -1);
    ll ans = 0;
    LCA lca; lca.build(adj);
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        ans += lca.dist(euler[i], euler[(i + n / 2) % n]);
        v[euler[i]] = euler[(i + n / 2) % n];
    }
    return {ans, v};
}
};

struct minimum{
    vector<int> v;
int ans = 0;

bool DFS(int x, vector<vector<int>>& adj, int p){
    vector<int> odd;
    for(int node : adj[x]){
        if(node == p) continue;
        bool rep = DFS(node, adj, x);
        if(rep) odd.push_back(node);
    }
    if(odd.size() == 0){
        if(x == 0){
            int node = adj[x][0];
            if(v[v[node]] == node){
                v[x] = v[node];
                v[node] = x;
                ans += 2;
            }else{
                int node1 = v[node];
                int node2 = v[v[node]];
                v[node1] = node2;
                v[node2] = node1;
                v[x] = node;
                v[node] = x;
                ans += 2;
            }
        }else return 1;
    }else{
        if(((int)odd.size()) % 2 == 1){
            for(int i = 1; i < (int)odd.size() - 1; i += 2){
                v[odd[i]] = odd[i + 1];
                v[odd[i + 1]] = odd[i];
                ans += 4;
            }
            v[x] = odd[0];
            v[odd[0]] = x;
            ans += 2;
        }else{
            for(int i = 2; i < (int)odd.size() - 1; i += 2){
                v[odd[i]] = odd[i + 1];
                v[odd[i + 1]] = odd[i];
                ans += 4;
            }
            v[x] = odd[0];
            v[odd[0]] = odd[1];
            v[odd[1]] = x;
            ans += 4;
        }
    }
    return 0;
}

pair<int, vector<int>> solve(vector<vector<int>> adj){
    int n = adj.size();
    v.resize(n);
    DFS(0, adj, -1);
    return {ans, v};
}
};

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

    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //int tt; cin >> tt;
    int n; cin >> n;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    minimum men;
    maximum mex;
    pair<int, vector<int>> mn = men.solve(adj);
    pair<ll, vector<int>> mx = mex.solve(adj);
    cout << mn.first << " "<< mx.first << endl;
    for(int x : mn.second) cout << x + 1 << " ";
    cout << endl;
    for(int x : mx.second) cout << x + 1 << " ";
    cout << endl;
}

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