Submission #349530

#	Time	Username	Problem	Language	Result	Execution time	Memory
349530		parsabahrami	Swapping Cities (APIO20_swap)	C++17	100 / 100	369 ms	43572 KiB

swap

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

typedef long long int ll;
typedef pair<int, int > pii;

#define SZ(x)               (int) x.size()
#define F                   first
#define S                   second

const int N = 3e5 + 10;
int P[20][N], H[N], C[N], rt[N], D[N], M[N], tim;

int Find(int v) {
    return !rt[v] ? v : rt[v] = Find(rt[v]);
}

void Union(int u, int v, int w) {
    u = Find(u), v = Find(v);
    if (u == v) {
        ++tim;
        P[0][u] = rt[u] = P[0][tim] = tim;
        C[u] = w; M[tim] = 1;
    } else {
        ++tim;
        rt[u] = rt[v] = P[0][u] = P[0][v] = P[0][tim] = tim;
        C[u] = C[v] = w;
        M[tim] = M[u] | M[v];
    }
}

void init(int n, int m,
          vector<int> U, vector<int> V, vector<int> W) {
    tim = n - 1; vector<pair<int, pii>> E;
    for (int i = 0; i < m; i++) {
        E.push_back({W[i], {U[i], V[i]}});
    }
    sort(E.begin(), E.end());
    for (auto e : E) {
        int w = e.F, u = e.S.F, v = e.S.S;
        D[u]++, D[v]++;
        Union(u, v, w);
        if (D[u] > 2 || D[v] > 2) M[Find(u)] = 1;
    }
    for (int i = 1; i < 20; i++) for (int j = 0; j <= tim; j++) P[i][j] = P[i - 1][P[i - 1][j]];
    for (int i = tim - 1; i >= 0; i--) H[i] = H[P[0][i]] + 1;
}

int getMinimumFuelCapacity(int u, int v) {
    if (H[u] < H[v]) swap(u, v);
    for (int i = H[u] - H[v]; i; i -= i & -i) u = P[__builtin_ctz(i)][u];
    for (int i = 19; ~i; i--) {
        if (P[i][u] != P[i][v] || !M[P[i][v]]) {
            u = P[i][u], v = P[i][v];
        }
    }
    if (P[0][u] != P[0][v]) return -1;
    if (!M[P[0][u]]) return -1;
    return C[u];
}

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