Submission #565354

#	Time	Username	Problem	Language	Result	Execution time	Memory
565354		Ooops_sorry	Swapping Cities (APIO20_swap)	C++14	100 / 100	596 ms	61924 KiB

swap

#include<bits/stdc++.h>
#ifndef LOCAL
    #include "swap.h"
#endif // LOCAL

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 3e5 + 10;
vector<int> g[N];
bool good[N];
int par[N], sz[N], d[N], po[20][N], val[N];

int find_set(int v) {
    if (v == par[v]) return v;
    else return par[v] = find_set(par[v]);
}

void union_set(int a, int b) {
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    par[b] = a;
    sz[a] += sz[b];
    good[a] |= good[b];
}

void dfs(int v, int p) {
    po[0][v] = p;
    for (auto to : g[v]) {
        if (to != p) {
            d[to] = d[v] + 1;
            dfs(to, v);
        }
    }
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    for (int i = 0; i < N; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    vector<int> ord(m), ind(n), cnt(n);
    iota(ind.begin(), ind.end(), 0);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){return w[i] < w[j];});
    int now = n;
    for (auto i : ord) {
        int a = find_set(u[i]), b = find_set(v[i]);
        val[now] = w[i];
        if (a == b) {
            po[0][ind[a]] = now;
            g[now].pb(ind[a]);
            good[a] = good[now] = 1;
            ind[a] = now++;
        } else {
            po[0][ind[a]] = now;
            po[0][ind[b]] = now;
            g[now].pb(ind[a]);
            g[now].pb(ind[b]);
            union_set(a, b);
            cnt[u[i]]++, cnt[v[i]]++;
            a = find_set(a);
            good[a] |= max(cnt[u[i]], cnt[v[i]]) >= 3;
            good[now] = good[a];
            ind[a] = now++;
        }
    }
    dfs(now - 1, now - 1);
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < now; j++) {
            po[i][j] = po[i - 1][po[i - 1][j]];
        }
    }
}

int lca(int a, int b) {
    if (d[a] < d[b]) swap(a, b);
    for (int i = 19; i >= 0; i--) {
        if (d[po[i][a]] >= d[b]) {
            a = po[i][a];
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (po[i][a] != po[i][b]) {
            a = po[i][a];
            b = po[i][b];
        }
    }
    return po[0][a];
}

int getMinimumFuelCapacity(int a, int b) {
    int l = lca(a, b);
    if (!good[l]) {
        for (int i = 19; i >= 0; i--) {
            if (!good[po[i][l]]) {
                l = po[i][l];
            }
        }
        if (d[l] > 0) {
            l = po[0][l];
        }
        if (good[l]) {
            return val[l];
        } else {
            return -1;
        }
    } else {
        return val[l];
    }
}

#ifdef LOCAL

signed main() {
    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

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