Submission #1123246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123246		adaawf	Swapping Cities (APIO20_swap)	C++20	100 / 100	323 ms	57344 KiB

swap

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int p[300005], f[300005], ff[300005], d[300005], dd[300005], b[300005], l[300005][19], da[300005];
vector<int> g[300005];
int Find(int x) {
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}
void Merge(int x, int y, int i) {
    d[x]++; d[y]++;
    int fl = 0;
    if (d[x] >= 3 || d[y] >= 3) fl = 1;
    x = Find(x);
    y = Find(y);
    if (x == y) fl = 1;
    fl |= f[x] | f[y];
    f[i] = fl;
    p[x] = p[y] = i;
    g[i].push_back(x);
    if (x != y) g[i].push_back(y);
    dd[x] = dd[y] = 1;
}
void dfs(int x, int p, int h) {
    l[x][0] = p;
    if (f[x] == 1) h = b[x];
    ff[x] = h;
    for (int w : g[x]) {
        da[w] = da[x] + 1;
        dfs(w, x, h);
    }
}
int lca(int x, int y) {
    if (da[x] < da[y]) swap(x, y);
    int k = da[x] - da[y];
    for (int i = 0; i < 19; i++) {
        if (k & (1 << i)) {
            x = l[x][i];
        }
    }
    if (x == y) return x;
    for (int i = 18; i >= 0; i--) {
        if (l[x][i] != l[y][i]) {
            x = l[x][i];
            y = l[y][i];
        }
    }
    return l[x][0];
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    vector<pair<int, pair<int, int>>> a;
    for (int i = 0; i < m; i++) {
        a.push_back({w[i], {u[i], v[i]}});
    }
    for (int i = 0; i < n + m; i++) p[i] = i;
    sort(a.begin(), a.end());
    for (int i = 0; i < m; i++) {
        Merge(a[i].second.first, a[i].second.second, i + n);
        b[i + n] = a[i].first;
    }
    for (int i = 0; i < n + m; i++) {
        if (dd[i] == 0) {
            dfs(i, n + m, 0);
        }
    }
    for (int i = 0; i <= 18; i++) l[n + m][i] = n + m;
    for (int i = 1; i <= 18; i++) {
        for (int j = 0; j < n + m; j++) {
            l[j][i] = l[l[j][i - 1]][i - 1];
        }
    }
}
int getMinimumFuelCapacity(int x, int y) {
    int h = ff[lca(x, y)];
    if (h == 0) return -1;
    return h;
}

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