Submission #571165

#	Time	Username	Problem	Language	Result	Execution time	Memory
571165		SlavicG	Swapping Cities (APIO20_swap)	C++17	100 / 100	670 ms	84440 KiB

swap

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 4e5 + 10, K = 25;
vector<int> adj[N], g[N];
int val[N], degree[N], depth[N], jump[N][K], id, n;
bool vis[N], good;


struct DSU {
    vector<int> par;
    DSU() {
        par.assign(N, 0);
        forn(i, N) par[i] = i;
    }
    int get(int a) {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }
    void uni(int a, int b) {
        a = get(a);
        b = get(b);
        par[a] = b;
    }
};
vector<int> component;

void get_component(int u) {
    vis[u] = true;
    component.pb(u);
    for(int v: g[u]) {
        if(!vis[v]) get_component(v);
    }
}

void dfs(int u, int par) {
    jump[u][0] = par;
    for(int v: adj[u]) {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int LCA(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);

    for(int j = K - 1; j >= 0; --j) {
        if(depth[jump[u][j]] >= depth[v]) {
            u = jump[u][j];
        }
    }
    //cout << u << ' ' << v << ' ' << depth[u] << ' ' << depth[v] << endl;
    if(u == v) return u;
    for(int j = K - 1; j >= 0; --j) {
        if(jump[u][j] != jump[v][j]) {
            u = jump[u][j], v = jump[v][j];
        }
    }
    //cout << u << ' ' << jump[u][0] << endl;
    return jump[u][0];
}

void init(int _n, int m, vector<int> U, vector<int> V, vector<int> W) {
    n = _n;
    id = n;

    vector<array<int, 3>> edges;
    DSU d;
    DSU connect;
    for(int i = 0; i < m; ++i) {
        edges.pb({W[i], U[i], V[i]});
    }
    sort(all(edges));
    
    for(auto x: edges) {
        int u = x[1], v = x[2], w = x[0];
        
        g[u].pb(v);
        g[v].pb(u);

        if(d.get(u) == d.get(v)) continue;
        if(d.get(u) == u) swap(u, v);

        if(d.get(u) != u && d.get(v) != v) {
            adj[id].pb(d.get(u));
            adj[id].pb(d.get(v));
            d.uni(u, id);
            d.uni(v, id);
            val[id] = w;
            ++id;
        } else if(d.get(u) != u) {
            component.clear();
            get_component(v);
            for(auto x: component) {
                adj[id].pb(x);
                d.uni(x, id);
            }
            val[id] = w;
            ++id;

            adj[id].pb(d.get(u));
            adj[id].pb(d.get(v));
            d.uni(u, id);
            d.uni(v, id);
            val[id] = w;
            ++id;
        } else {
            ++degree[u];
            ++degree[v];
            if(connect.get(u) == connect.get(v) || degree[u] > 2 || degree[v] > 2) {
                component.clear();
                get_component(u);
                good = true;
                for(auto x: component) {
                    d.uni(x, id);
                    adj[id].pb(x);
                }
                
                val[id] = w;
                ++id;
            } else{
                connect.uni(u, v);
            }

        }
    }
    
    dfs(id - 1, id - 1);
    for(int k = 1; k < K; ++k) {
        for(int i = 0; i < N; ++i) {
            jump[i][k] = id - 1;
        }
    }

    for(int k = 1; k < K; ++k) {
        for(int i = 0; i < N; ++i) {
            jump[i][k] = jump[jump[i][k - 1]][k - 1];
        }
    }

    
}

int getMinimumFuelCapacity(int u, int v) {
    if(!good) return -1;
    return val[LCA(u, v)];
}

/*
void solve() {  
    int NN, m; cin >> NN >> m;
    vector<int> a(m), b(m), c(m);
    forn(i, m) cin >> a[i];
    forn(i, m) cin >> b[i];
    forn(i, m) cin >> c[i];
    init(NN, m, a, b, c);
    cout << getMinimumFuelCapacity(1, 2) << "\n";
    cout << getMinimumFuelCapacity(2, 4) << "\n";
    cout << getMinimumFuelCapacity(0, 1) << "\n";
    
}   
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}
*/

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