Submission #569604

#	Time	Username	Problem	Language	Result	Execution time	Memory
569604		tranxuanbach	Swapping Cities (APIO20_swap)	C++17	100 / 100	378 ms	55880 KiB

swap

#ifndef FEXT

#include "swap.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e5 + 5, M = 2e5 + 5, K = 3e5 + 5, LK = 19;

struct edge_t{
    int u, v, w;

    edge_t(){

    }

    edge_t(int u, int v, int w): u(u), v(v), w(w){

    }

    friend bool operator< (const edge_t &lhs, const edge_t &rhs){
        return lhs.w < rhs.w;
    }
};

struct disjoint_set_union{
    int par[N], node[N];
    vi path[N];

    void reset(){
        For(i, 0, N){
            par[i] = -1;
            node[i] = i;
            path[i].emplace_back(i);
        }
    }

    disjoint_set_union(){
        reset();
    }

    int root(int x){
        return par[x] < 0 ? x : (par[x] = root(par[x]));
    }

    void merge(int x, int y){
        if ((x = root(x)) == (y = root(y))){
            return;
        }
        if (par[x] > par[y]){
            swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        while (!path[y].empty()){
            path[x].emplace_back(path[y].back());
            path[y].pop_back();
        }
    }
} dsu;

int n, m;
edge_t a[M];

bool b[N];
int deg[N];

int k;
int c[K];
vi adj[K];

int par[K][LK];
int h[K];

void dfs(int u){
    For(j, 1, LK){
        par[u][j] = par[par[u][j - 1]][j - 1];
    }
    Fora(v, adj[u]){
        par[v][0] = u;
        h[v] = h[u] + 1;
        dfs(v);
    }
}

void init(int _n, int _m, vi _u, vi _v, vi _w){
    n = _n; m = _m;
    ForE(i, 1, m){
        a[i] = edge_t(_u[i - 1] + 1, _v[i - 1] + 1, _w[i - 1]);
    }

    k = n;
    memset(c, -1, sizeof(c));
    dsu.reset();

    sort(a + 1, a + m + 1);
    ForE(i, 1, m){
        int u = a[i].u, v = a[i].v, w = a[i].w;
        if (dsu.root(u) == dsu.root(v)){
            if (!b[u]){
                int tu = dsu.node[dsu.root(u)];
                c[tu] = w;
                Fora(t, dsu.path[dsu.root(u)]){
                    b[t] = 1;
                }
            }
        }
        else{
            if (deg[u] < deg[v]){
                swap(u, v);
            }

            int tu = dsu.node[dsu.root(u)], tv = dsu.node[dsu.root(v)];
            k++;
            adj[k].emplace_back(tu);
            adj[k].emplace_back(tv);

            if (b[u] and b[v]){
                c[k] = w;
            }
            else if (b[u]){
                c[k] = w;
                Fora(t, dsu.path[dsu.root(v)]){
                    b[t] = 1;
                }
            }
            else if (b[v]){
                c[k] = w;
                Fora(t, dsu.path[dsu.root(u)]){
                    b[t] = 1;
                }
            }
            else{
                if (deg[u] >= 2){
                    c[k] = w;
                    Fora(t, dsu.path[dsu.root(u)]){
                        b[t] = 1;
                    }
                    Fora(t, dsu.path[dsu.root(v)]){
                        b[t] = 1;
                    }
                }
            }
            dsu.merge(u, v);
            dsu.node[dsu.root(u)] = k;
        }
        deg[u]++; deg[v]++;
    }
    dfs(k);
}

int lca(int u, int v){
    if (h[u] < h[v]){
        swap(u, v);
    }
    FordE(i, LK - 1, 0){
        if (h[u] - (1 << i) >= h[v]){
            u = par[u][i];
        }
    }
    if (u == v){
        return u;
    }
    FordE(i, LK - 1, 0){
        if (par[u][i] != par[v][i]){
            u = par[u][i]; v = par[v][i];
        }
    }
    return par[u][0];
}

int getMinimumFuelCapacity(int u, int v){
    u++; v++;

    int t = lca(u, v);
    if (c[t] != -1){
        return c[t];
    }
    FordE(i, LK - 1, 0){
        if (par[t][i] != 0 and c[par[t][i]] == -1){
            t = par[t][i];
        }
    }
    t = par[t][0];
    if (t != 0){
        return c[t];
    }
    return -1;
}

#ifdef FEXT

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == scanf("%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == scanf("%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", minimum_fuel_capacities[i]);
    }

    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
--------------------------------------------------|
3 2
0 1 5
0 2 5
1
1 2
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3
10
4
--------------------------------------------------|
-1
--------------------------------------------------|
==================================================+
*/

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