Submission #965722

#	Time	Username	Problem	Language	Result	Execution time	Memory
965722		phoenix0423	Swapping Cities (APIO20_swap)	C++17	6 / 100	228 ms	41196 KiB

swap

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#include "swap.h"

namespace{
    const int maxn = 3e5 + 5;
    const int INF = 1e9 + 7;
    struct DSU{
        vector<int> par, siz;
        int n;
        DSU(){}
        DSU(int _n) : n(_n){
            par.resize(n);
            siz.resize(n, 1);
            iota(par.begin(), par.end(), 0);
        }
        int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);}
        void unite(int x, int y){
            x = root(x), y = root(y);
            if(x == y) return;
            if(siz[x] > siz[y]) swap(x, y);
            par[x] = y, siz[y] += siz[x];
        }
    } dsu;
    struct edge{
        int u, v, w;
        edge(){}
        edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w){}
        bool operator < (const edge& other) const{
            return w < other.w;
        }
    };
    int par[maxn], w[maxn], k[maxn], dep[maxn], succ[maxn][19], mn[maxn];
    vector<int> adj[maxn];
}

void dfs(int pos, int prev, int nd){
    if(k[pos]) nd = w[pos];
    mn[pos] = nd;
    succ[pos][0] = prev;
    for(int i = 1; i < 19; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    for(auto x : adj[pos]){
        dep[x] = dep[pos] + 1;
        dfs(x, pos, nd);
    }
}
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W){
    dsu = DSU(n);
    vector<edge> e;
    for(int i = 0; i < m; i++) e.pb(edge(U[i], V[i], W[i]));
    sort(e.begin(), e.end());
    vector<int> b(n);
    iota(b.begin(), b.end(), 0);
    int id = n;
    for(auto [u, v, wg] : e){
        u = dsu.root(u), v = dsu.root(v);
        if(u == v){
            int x = b[u];
            if(k[x]) continue;
            int nw = id++;
            adj[nw].pb(x);
            par[x] = nw;
            w[nw] = wg; 
            k[nw] = 1;
            b[u] = nw;
        }
        else{
            dsu.unite(u, v);
            int nw = id++;
            w[nw] = wg, k[nw] = k[b[u]] | k[b[v]];
            par[b[u]] = nw, par[b[v]] = nw;
            adj[nw].pb(b[u]), adj[nw].pb(b[v]);
            b[u] = nw, b[v] = nw;
        }
    }
    dfs(id - 1, id - 1, INF);
}

int lift(int x, int steps){
    for(int i = 18; i >= 0; i--){
        if(steps & (1 << i)) x = succ[x][i];
    }
    return x;
}

int find_lca(int x, int y){
    if(dep[x] > dep[y]) swap(x, y);
    y = lift(y, dep[y] - dep[x]);
    if(x == y) return x;
    for(int i = 18; i >= 0; i--){
        if(succ[x][i] != succ[y][i]) x = succ[x][i], y = succ[y][i];
    }
    return succ[x][0];
}
int getMinimumFuelCapacity(int x, int y){
    int lca = find_lca(x, y);
    if(mn[lca] == INF) mn[lca] = -1;
    return mn[lca];
}

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