Submission #1160262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160262		ProtonDecay314	Village (BOI20_village)	C++20	100 / 100	189 ms	46128 KiB

Village

/*
Output

min max
minconfig
maxconfig
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
#define pb push_back
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()

template<typename T>
void print_vec(const vector<T>& v) {
    for(T vv : v) cerr << vv << " ";
    cerr << "\n";
}

template<typename T>
void print_perm_array(const vector<T>& v) {
    for(T vv : v) cout << vv + 1ll << " ";
    cout << endl;
}

vll find_centroid(const vvll& adj, const vll& outdeg) {
    vll outdegc = outdeg;

    ll n = adj.size();
    /*
    ll found = 0ll;

    // BFS to remove noncentroids
    vll to_remove;
    vb vis(n, false);

    for(ll i = 0ll; i < n; i++) if(outdegc[i] == 1ll) to_remove.pb(i);

    while(found < n - 2ll) {
        // Remove all in to_remove
        vll next_to_remove;
        for(ll i : to_remove) {
            outdegc[i] = 0ll;
            found++;
            vis[i] = true;
            for(ll j : adj[i]) {
                outdegc[j]--;
                if(outdegc[j] == 1ll) next_to_remove.pb(j);
            }
        }

        to_remove = next_to_remove;
    }

    vll centroids;

    for(ll i = 0ll; i < n; i++) if(!vis[i]) centroids.pb(i);
    */

    // Note: the cod above is wrong because it finds the CENTERS of the tree, not the centroids
    vll centroids;
    vll size(n, 0ll);

    function<void(int, int)> dfs = [&](int i, int prv) {
        size[i] = 1ll;
        
        bool centroid = true;
        for(ll j : adj[i]) if(j != prv) {
            dfs(j, i);
            size[i] += size[j];
            if(size[j] > (n >> 1ll)) centroid = false; // Check if the other subtree violates the centroid property
        }
        if(n - size[i] > (n >> 1ll)) centroid = false; // Check if this subtree violates the centroid property
        if(centroid) centroids.pb(i);
    };
    dfs(0, 0);

    return centroids;
}

vvll partition(const vvll& adj, const vll& centroid) {
    ll n = adj.size();

    vll colors(n, -1ll);

    queue<pll> q;
    ll cur_color = 0ll;
    for(ll i : adj[centroid[0ll]]) {
        q.push({i, cur_color});
        cur_color++;
    }

    vb vis(n, false);

    while(!q.empty()) {
        auto [i, color] = q.front();
        q.pop();

        if(vis[i]) continue;
        vis[i] = true;
        colors[i] = color;

        for(ll j : adj[i]) q.push({j, color});
    }

    // Creating color partitions
    vvll partitions;
    for(ll i = 0ll; i < cur_color; i++) {
        vll partitionsr;
        partitions.pb(partitionsr);
    }

    for(ll i = 0ll; i < n; i++) {
        if(i == centroid[0ll]) continue;
        partitions[colors[i]].pb(i);
    }

    return partitions;
}

vll solve_min(const vvll& adj, const vll& deg) {
    vll degc = deg;
    ll n = adj.size();
    vll ans(n, -1ll);
    vll comp(n, -1ll);
    // print_vec(deg);
    
    // Create queue
    queue<ll> q;
    
    // Initializing queues
    for(ll i = 0ll; i < n; i++) {
        if(degc[i] == 1ll) q.push(i);
    }
    
    // BFS
    ll id = 0ll;
    
    while(!q.empty()) {
        ll i = q.front();
        q.pop();
        
        if(degc[i] < 1ll) continue;
        
        // Identify center of the star subgraph
        ll j = -1ll;
        for(ll jp : adj[i]) {
            if(degc[jp] >= 1ll) j = jp;
        }
        
        // Deactivate each neighbor of the star subgraph
        // if it is a leaf
        for(ll k : adj[j]) {
            if(degc[k] == 1ll) {
                comp[k] = id;
                degc[k] = 0ll;
            } else {
                degc[k]--;
                if(degc[k] == 1ll) q.push(k);
            }
        }
        
        // Deactivate the center
        degc[j] = 0ll;
        comp[j] = id;
        // print_vec(degc);
        
        id++;
    }
    
    // Create an array of arrays containing all the nodes in each conneted component
    vvll comps;
    for(ll i = 0ll; i < id; i++) {
        vll compsr;
        comps.pb(compsr);
    }

    // print_vec(comp);
    for(ll i = 0ll; i < n; i++) {
        comps[comp[i]].pb(i);
    }
    
    // cerr << "EGAITA MIRAI WA" << endl;
    // Generating solution
    for(ll i = 0ll; i < id; i++) {
        ll csize = comps[i].size();
        for(ll j = 0ll; j < csize - 1ll; j++) {
            ans[comps[i][j]] = comps[i][j + 1ll];
        }

        ans[comps[i].back()] = comps[i][0ll];
    }

    return ans;
}

vll solve_max(const vvll& adj, const vll& centroids) {
    ll n = adj.size();

    /*
    n is even:
    all can be paired
    there will be a single unpaired node---pair it with the centroid

    n is odd:
    choose one pair and reroute it so that it goes
    a -> centroid -> b -> a

    instead of a -> b -> a
    */

    /*
    Algo:
    1. Partition the graph into subtrees using one of the centroids
    2. Keep track of subtree sizes AND subtree contents
    3. Make a MAX priority queue of subtree sizes
    4. At each step, pop off the two largest subtrees from the MAX pqueue
        4a. if one or both of them are zero, terminate
        4b. Pair the two nodes otherwise
        4c. Reinsert the two subtrees into the priority queue but with one less item
    */

    // 1. Partition the graph into subtrees
    // 2. Keep track of subtree sizes AND subtree contents
    vvll partitions = partition(adj, centroids);
    ll num_partitions = partitions.size();

    // 3. Make a MAX priority queue of subtree sizes
    typedef priority_queue<pll, vector<pll>, less<pll>> pqueue;

    pqueue pq;

    for(ll i = 0ll; i < num_partitions; i++) {
        pq.push({partitions[i].size(), i});
    }

    vpll pairs;
    ll paired = 0ll;

    
    while(paired < n - 2ll) {
        auto [s1s, s1t] = pq.top();
        pq.pop();
        auto [s2s, s2t] = pq.top();
        pq.pop();

        
        pairs.pb({partitions[s1t].back(), partitions[s2t].back()});
        
        partitions[s1t].pop_back();
        partitions[s2t].pop_back();
        
        pq.push({s1s - 1ll, s1t});
        pq.push({s2s - 1ll, s2t});
        paired += 2ll;
    }
    
    // Getting ready to store results
    
    /*
    if n is even, pair the last with the centroid
    */
   if((n & 0b1ll) == 0ll) {
       pairs.pb({partitions[pq.top().second][0ll], centroids[0ll]});
    }
    
    ll num_pairs = pairs.size();
    vll res(n, -1ll);
    
    /*
    if n is odd, do something special with the first pairing
    */
   if(n & 0b1ll) {
        res[pairs[0ll].first] = centroids[0ll];
        res[centroids[0ll]] = pairs[0ll].second;
        res[pairs[0ll].second] = pairs[0ll].first;
    }

    
    for(ll i = (n & 0b1ll); i < num_pairs; i++) {
        auto [u, v] = pairs[i];
        
        res[u] = v;
        res[v] = u;
    }
    
    return res;
}

vll compute_depths(const vvll& adj, ll s) {
    queue<pll> q;
    q.push({s, 0ll});

    ll n = adj.size();
    vll depths(n, 0ll);

    vb vis(n, false);

    while(!q.empty()) {
        auto [i, dep] = q.front();
        q.pop();

        if(vis[i]) continue;
        vis[i] = true;
        depths[i] = dep;

        for(ll j : adj[i]) q.push({j, dep+1ll});
    }

    return depths;
}

vll compute_par_array(ll s, const vvll& adj) {
    queue<pll> q;
    q.push({s, s});

    ll n = adj.size();
    vll par(n, 0ll);

    while(!q.empty()) {
        auto [i, prev] = q.front();
        q.pop();

        par[i] = prev;

        for(ll j : adj[i]) if(j != prev) q.push({j, i});
    }

    return par;
};

vvll compute_jmp_pointers(const vll& par) {
    ll n = par.size();
    vvll jmp;
    for(ll i = 0ll; i < n; i++) {
        vll jmpr(20ll, -1ll);
        jmp.pb(jmpr);
    }

    for(ll i = 0ll; i < n; i++) jmp[i][0ll] = par[i];

    for(ll rep = 1ll; rep < 20ll; rep++) {
        for(ll i = 0ll; i < n; i++) {
            jmp[i][rep] = jmp[jmp[i][rep - 1ll]][rep - 1ll];
        }
    }

    return jmp;
}

ll jmp_fixed(const vvll& jmp, ll i, ll to_jump) {
    for(ll pw = 19ll; pw >= 0ll; pw--) {
        if(to_jump >> pw) {
            to_jump ^= 1ll << pw;

            i = jmp[i][pw];
        }
    }

    return i;
}

ll lca(const vll& depths, const vvll& jmp, ll i, ll j) {
    ll pi = i, pj = j;

    ll dpi = depths[i], dpj = depths[j];

    if(dpi > dpj) pi = jmp_fixed(jmp, pi, dpi - dpj);
    if(dpj > dpi) pj = jmp_fixed(jmp, pj, dpj - dpi);

    if(pi == pj) return pj;

    for(ll pw = 19ll; pw >= 0ll; pw--) {
        if(jmp[pi][pw] != jmp[pj][pw]) {
            pi = jmp[pi][pw];
            pj = jmp[pj][pw];
        }
    }

    return jmp[pi][0ll];
}

ll dist(const vll& depths, const vvll& jmp, ll i, ll j) {
    return depths[i] + depths[j] - (depths[lca(depths, jmp, i, j)] << 1ll);
}

ll pairing_cost(const vll& pairing, const vll& depths, const vvll& jmp) {
    ll ans = 0ll;

    ll n = depths.size();

    for(ll i = 0ll; i < n; i++) {
        ans += dist(depths, jmp, i, pairing[i]);
    }

    return ans;
}

int main() {
    // Take Inputs, compute outdegree
    ll n;
    cin >> n;

    vvll adj;
    for(ll i = 0ll; i < n; i++) {
        vll adjr;
        adj.pb(adjr);
    }

    vll outdeg(n, 0ll);

    for(ll i = 0ll; i < n - 1ll; i++) {
        ll a, b;
        cin >> a >> b;
        a--;b--;

        adj[a].pb(b);
        adj[b].pb(a);
        outdeg[a]++;
        outdeg[b]++;
    }

    
    // Some more info to preprocess
    /// Computing depths
    vll centroids = find_centroid(adj, outdeg);
    
    vll depths = compute_depths(adj, centroids[0ll]);
    
    /// Parent array
    vll par = compute_par_array(centroids[0ll], adj);
    
    /// Jump pointers
    vvll jmp = compute_jmp_pointers(par);
    
    
    
    // Computing the answers
    vll min_case = solve_min(adj, outdeg);
    vll max_case = solve_max(adj, centroids);
    cout << pairing_cost(min_case, depths, jmp) << " " << pairing_cost(max_case, depths, jmp) << endl;
    print_perm_array(min_case);
    print_perm_array(max_case);
    return 0;
}

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