Submission #564987

#	Time	Username	Problem	Language	Result	Execution time	Memory
564987		Ooops_sorry	Swapping Cities (APIO20_swap)	C++14	0 / 100	2076 ms	66652 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);

struct vert {
    int u, mn, mx;
};

const int N = 2e5 + 10, INF = 1e9;
multiset<int> st[N];
vector<pair<int,int>> g[N];
int val[N], d[N], ed[N];
vert po[20][N];

struct dsu {
    vector<int> par, sz;
    dsu(int n) {
        par.resize(n);
        iota(par.begin(), par.end(), 0);
        sz.resize(n, 1);
    }
    int find_set(int v) {
        if (v == par[v]) return v;
        else return par[v] = find_set(par[v]);
    }
    bool union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a == b) return 0;
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        par[b] = a;
        sz[a] += sz[b];
        return 1;
    }
};

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

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].u] >= d[b]) {
            a = po[i][a].u;
        }
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--) {
        if (po[i][a].u != po[i][b].u) {
            a = po[i][a].u;
            b = po[i][b].u;
        }
    }
    return po[0][a].u;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    dsu d(n);
    vector<int> ord(m);
    for (int i = 0; i < n; i++) {
        st[i].insert(INF);
    }
    for (int i = 0; i < m; i++) {
        st[u[i]].insert(w[i]);
        st[v[i]].insert(w[i]);
    }
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j){return w[i] < w[j];});
    for (auto i : ord) {
        if (d.union_set(u[i], v[i])) {
            st[u[i]].erase(st[u[i]].find(w[i]));
            st[v[i]].erase(st[v[i]].find(w[i]));
            g[u[i]].pb({v[i], w[i]});
            g[v[i]].pb({u[i], w[i]});
        }
    }
    for (int i = 0; i < n; i++) {
        val[i] = *st[i].begin();
    }
    dfs(0, 0);
    po[0][0] = {0, val[0], -INF};
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            int v = po[i - 1][j].u;
            po[i][j] = {po[i - 1][v].u, min(po[i - 1][j].mn, po[i - 1][v].mn), max(po[i - 1][j].mx, po[i - 1][v].mx)};
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    assert(x != y);
    int mn = INF, mx = -INF, g = lca(x, y);
    mn = val[g];
    while (x != g) {
        mx = max(mx, ed[x]);
        mn = min(mn, val[x]);
        x = po[0][x].u;
    }
    while (y != g) {
        mx = max(mx, ed[y]);
        mn = min(mn, val[y]);
        y = po[0][y].u;
    }
    if (mn == INF)  return -1;
    return max(mn, mx);
}

#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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27