Submission #403341

#	Time	Username	Problem	Language	Result	Execution time	Memory
403341		danielcm585	Swapping Cities (APIO20_swap)	C++14	100 / 100	413 ms	43848 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const int N = 3e5;
const int LOG = 19;
int par[N+2], val[N+2], deg[N+2], dep[N+2];
int anc[N+2][LOG+2];

int find(int x) {
    if (par[x] == x) return x;
    return par[x] = find(par[x]);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < N+M; i++) {
        par[i] = i;
        anc[i][0] = i;
        val[i] = -1;
    }
    vector<iii> edge;
    for (int i = 0; i < M; i++) {
        edge.push_back({W[i],{U[i],V[i]}});
    }
    sort(edge.begin(),edge.end());
    for (int i = 0; i < M; i++) {
        int u = edge[i].se.fi;
        int v = edge[i].se.se;
        int w = edge[i].fi;
        int pu = find(u);
        int pv = find(v);
        deg[u]++, deg[v]++;
        par[pu] = par[pv] = N+i;
        anc[pu][0] = anc[pv][0] = N+i;
        val[N+i] = -1;
        if (deg[u] >= 3 || deg[v] >= 3 || pu == pv || val[pu] != -1 || val[pv] != -1) val[N+i] = w;
    }
    for (int i = 1; i <= LOG; i++) {
        for (int j = 0; j < N+M; j++) {
            anc[j][i] = anc[anc[j][i-1]][i-1];
        }
    }
    for (int i = N+M-2; i >= 0; i--) {
        dep[i] = dep[anc[i][0]]+1;
    }
}

int lca(int X, int Y) {
    if (dep[X] < dep[Y]) swap(X,Y);
    for (int i = LOG; i >= 0; i--) {
        if (dep[X]-(1<<i) >= dep[Y]) {
            X = anc[X][i];
        }
    }
    if (X == Y) return X;
    for (int i = LOG; i >= 0; i--) {
        if (anc[X][i] != anc[Y][i]) {
            X = anc[X][i];
            Y = anc[Y][i];
        }
    }
    return anc[X][0];
}

int getMinimumFuelCapacity(int X, int Y) {
    if (find(X) != find(Y)) return -1;
    int z = lca(X,Y);
    // cout << ">> " << z << '\n';
    if (val[z] != -1) return val[z];
    for (int i = LOG; i >= 0; i--) {
        if (dep[z] < (1<<i)) continue;
        if (val[anc[z][i]] == -1) z = anc[z][i];
    }
    return val[anc[z][0]];
}

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

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