Submission #1109723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109723		Mike_Vu	Swapping Cities (APIO20_swap)	C++14	100 / 100	256 ms	71184 KiB

swap

#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct edge{
    int u, v, w;
    edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};

const int maxn = 3e5+5, lg = 19;
int n, m, trsz;
vector<edge> edges;
bool can[maxn];
int ans[maxn];
vector<int> adj[maxn];
int par[maxn][lg+1], h[maxn];
bool hadcan[maxn][lg+1];

namespace dsu{
    vector<int> dsu, deg, sumdeg;
    void init() {
        trsz = n;
        memset(can, 0, sizeof(can));
        dsu.assign(trsz+1, 0);
        deg.assign(trsz+1, 0);
        sumdeg.assign(trsz+1, 1);
        for (int i = 1; i <= n; i++) {
            dsu[i] = i;
        }
    }
    int f(int u) {
        if (u == dsu[u]) return u;
        return dsu[u] = f(dsu[u]);
    }
    void addedge(int u, int v) {
        int ru = f(u), rv = f(v);
        ++trsz;
        dsu.pb(trsz);
        dsu[ru] = dsu[rv] = trsz;
        adj[trsz].pb(ru);
        if (ru != rv) adj[trsz].pb(rv);
        ++deg[u];
        ++deg[v];
        //check cycle
        sumdeg.pb(sumdeg[ru]);
        if (ru != rv) sumdeg[trsz] += sumdeg[rv];
        if (deg[u] == 2)--sumdeg[trsz];
        if (deg[v] == 2)--sumdeg[trsz];
//        cout << u << ' ' << v << ' ' << trsz << "\n" << deg[u] << ' ' << deg[v] << ' ' << sumdeg[ru] << ' ' << sumdeg[rv] << ' ' << sumdeg[trsz] << "\n";
        can[trsz] = (max(deg[u], deg[v])>2 || sumdeg[trsz] == 0);
        can[trsz] |= can[ru] | can[rv];
    }
}

void dfs(int u) {
    //setup binlift
    for (int j = 1; j <= lg; j++) {
        par[u][j] = par[par[u][j-1]][j-1];
        hadcan[u][j] = hadcan[u][j-1]|hadcan[par[u][j-1]][j-1];
    }
    //dfs
    for (int v : adj[u]) {
        par[v][0] = u;
        hadcan[v][0] = can[u];
        h[v] = h[u]+1;
        dfs(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    if (h[u] > h[v]) {
        int k = h[u]-h[v];
        for (int j = lg; j >= 0; j--) {
            if (BITj(k, j)) {
                u = par[u][j];
            }
        }
    }
    if (u == v) return u;
    for (int j = lg; j >= 0; j--) {
        while (h[u] > MASK(j) && par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

int findnearest(int u){
    for (int j = lg; j >= 0; j--) {
        while (h[u] > MASK(j) && !hadcan[u][j]) {
            u = par[u][j];
        }
    }
    return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    //transform to normal use
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        int u = U[i]+1, v = V[i]+1, w = W[i];
        edges.pb(edge(u, v, w));
    }
    //build dsu tree
    sort(edges.begin(), edges.end(), [&](edge a, edge b){return a.w<b.w;});
    dsu::init();
    for (int i= 0; i < m; i++) {
        dsu::addedge(edges[i].u, edges[i].v);
        ans[trsz] = edges[i].w;
    }
    //build binlift
    memset(par, 0, sizeof(par));
    memset(hadcan, 0, sizeof(hadcan));
    h[trsz] = 1;
    dfs(trsz);
//    for (int i = trsz; i; i--) {
//        cout << i << ' ' << h[i] << ' ' << can[i] << ' ' << ans[i] << "\n";
//    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int x = X+1, y = Y+1;
    //lca
    int l = lca(x, y);
    //check if lca can
    if (can[l]) {
        return ans[l];
    }
    //if not -> find nearest can
    l = findnearest(l);
    //case cannot
    if (!can[l]) return -1;
    return ans[l];
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N, M;
    cin >> N >> M;
    vector<int> U, V, W;
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        U.pb(u);
        V.pb(v);
        W.pb(w);
    }
    init(N,M,U,V,W);
    int Q;
    cin >> Q;
    while (Q--) {
        int X, Y;
        cin >> X >> Y;
        cout << getMinimumFuelCapacity(X,Y) << "\n";
    }
}
#endif // mikevui
/*
5 4
0 1 6
0 2 4
0 3 4
1 4 6
1
4 0

6

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
0 2
*/

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