Submission #1191575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191575		Br3ad	Swapping Cities (APIO20_swap)	C++20	100 / 100	373 ms	70000 KiB

swap

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct DSU{
    vector<int> parent, edge_cnt;
    vector<bool> swappable;

    DSU(int n){
        parent = vector<int>(n+1);
        iota(all(parent), 0);

        edge_cnt = vector<int>(n+1, 0);
        swappable = vector<bool>(n+1, false);
    }

    int find_parent(int p){
        return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
    }

    void merge(int a, int b){
        int pa = find_parent(a);
        int pb = find_parent(b);
        edge_cnt[a]++;
        edge_cnt[b]++;

        // Degree >= 3
        if(edge_cnt[a] >= 3) swappable[pa] = true;
        if(edge_cnt[b] >= 3) swappable[pb] = true;

        // Contains cycle
        if(pa == pb) swappable[pb] = true;

        parent[pa] = pb;
        if(swappable[pa]) swappable[pb] = true;
    }

    bool is_same_union(int a, int b){
        int pa = find_parent(a);
        int pb = find_parent(b);
        return (pa == pb);
    }
};

int _n, _m;
vector<tuple<int, int, int>> edge;

vector<vector<int>> adj, par;
vector<int> tin, tout, val;
vector<bool> node_swappable;

DSU dsu(0);

int timer = 0;
void tour(int cur, int prev = -1){
    tin[cur] = timer++;
    for(int child : adj[cur]){
        if(child == prev) continue;
        par[child][0] = cur;
        tour(child, cur);
    }
    tout[cur] = timer++;
}

bool isAnc(int child, int anc){
    return (tin[anc] <= tin[child] && tout[anc] >= tout[child]);
}

int get_swaplca(int a, int b){
    if(isAnc(a, b)) swap(a, b);
    int lca = a, cur = b;
    for(int i = 19; i >= 0; i--){
        int next_cur = par[cur][i];
        if(isAnc(a, next_cur) && node_swappable[next_cur]){
            lca = next_cur;
        }else {
            cur = next_cur;
        }
    }
    return lca;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    _n = n;
    _m = m;

    edge.clear();
    adj.clear(); adj.resize(n+m);
    par.resize(n+m, vector<int>(20));

    for(int i = 0; i < m; i++) edge.PB({w[i], u[i], v[i]});
    sort(all(edge));

    vector<int> index(n);
    iota(all(index), 0);

    tin.resize(n+m);
    tout.resize(n+m);
    val.resize(n+m, -1);
    node_swappable.resize(n+m, false);

    int index_counter = n;

    dsu = DSU(n);
    for(int i = 0; i < m; i++){
        auto [w, u, v] = edge[i];

        int pu = dsu.find_parent(u);
        int pv = dsu.find_parent(v);

        dsu.merge(u, v);
        
        int rep = dsu.find_parent(u);

        if(pu == pv){
            // Same union
            adj[index_counter].PB(index[rep]);
            adj[index[rep]].PB(index_counter);
        }else {
            // Merge union
            adj[index_counter].PB(index[pu]);
            adj[index_counter].PB(index[pv]);
            adj[index[pu]].PB(index_counter);
            adj[index[pv]].PB(index_counter);
        }
        
        val[index_counter] = w;
        node_swappable[index_counter] = dsu.swappable[rep];
        index[rep] = index_counter++;
    }

    par[index_counter-1][0] = index_counter-1;
    tour(index_counter-1);

    for(int i = 1; i < 20; i++){
        for(int j = 0; j < index_counter; j++){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
}

// Full solution
int getMinimumFuelCapacity(int x, int y){
    int lca = get_swaplca(x, y);
    return val[lca];
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27