Submission #1160180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160180		ProtonDecay314	Village (BOI20_village)	C++20	0 / 100	0 ms	324 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);
    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_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();
        if(s1s >= 0ll && s2s >= 0ll) {
            cout << "err" << endl;
            vll ans(n, 0ll);
            return ans;
        };
        
        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(n, 0ll);
    for(ll i = 0ll; i < n; i++) min_case[i] = i;
    
    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: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50