Submission #1139214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139214		OI_Account	Swapping Cities (APIO20_swap)	C++20	100 / 100	234 ms	41556 KiB

swap

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

const int N = 100'000;
const int E = 200'000;
const int M = 18;
const int INF = 1'000'000'100;

int n, m, deg[N + 10], h[N + 10];
int x[E + 10], y[E + 10], w[E + 10];
int dp[N + 10][M + 3], sp[N + 10][M + 3];
int par[N + 10], mark3[N + 10], markC[N + 10];
int val3[N + 10], valC[N + 10];
vector<pair<int, int>> adj[N + 10], edge;
vector<int> cmp[N + 10];

void readInput(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    for (int i = 1; i <= m; i++) {
        x[i] = U[i - 1] + 1;
        y[i] = V[i - 1] + 1;
        w[i] = W[i - 1];
        edge.push_back({w[i], i});
    }
}

int getPar(int u) {
    return (par[u] < 0? u: (par[u] = getPar(par[u])));
}

void addMark3(int u, int w) {
    u = getPar(u);
    if (mark3[u])
        return;
    mark3[u] = true;
    for (auto v: cmp[u])
        val3[v] = min(val3[v], w);
}

void addMarkC(int u, int w) {
    u = getPar(u);
    if (markC[u])
        return;
    markC[u] = true;
    for (auto v: cmp[u])
        valC[v] = min(valC[v], w);
}

bool merg(int u, int v, int w) {
    deg[u]++;
    deg[v]++;
    if (deg[u] >= 3 || deg[v] >= 3) {
        addMark3(u, w);
        addMark3(v, w);
    }
    if ((u = getPar(u)) == (v = getPar(v))) {
        addMarkC(u, w);
        return false;
    }
    if (par[v] < par[u])
        swap(u, v);
    if (mark3[u] != mark3[v])
        addMark3((mark3[u]? v: u), w);
    if (markC[u] != markC[v])
        addMarkC((markC[u]? v: u), w);
    while (cmp[v].size()) {
        cmp[u].push_back(cmp[v].back());
        cmp[v].pop_back();
    }
    cmp[v].shrink_to_fit();
    par[u] += par[v];
    par[v] = u;
    return true;
}

void addEdge(int u, int v,int w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

void checkEdges() {
    for (int i = 1; i <= n; i++) {
        cmp[i].push_back(i);
        par[i] = -1;
        val3[i] = valC[i] = INF;
    }
    sort(edge.begin(), edge.end());
    for (auto [weight, e]: edge)
        if (merg(x[e], y[e], w[e]))
            addEdge(x[e], y[e], w[e]);
}

void dfs(int u = 1, int par = 0, int wUp = 0) {
    h[u] = h[par] + 1;
    dp[u][0] = par;
    sp[u][0] = wUp;
    for (int j = 1; j <= M && dp[u][j - 1]; j++) {
        dp[u][j] = dp[dp[u][j - 1]][j - 1];
        sp[u][j] = max(sp[u][j - 1], sp[dp[u][j - 1]][j - 1]);
    }
    for (auto [v, w]: adj[u])
        if (v != par)
            dfs(v, u, w);
}

int maxPath(int u, int v) {
    if (h[u] < h[v])
        swap(u, v);
    int res = 0;
    for (int j = M; j >= 0; j--)
        if (h[u] - h[v] >= (1 << j)) {
            res = max(res, sp[u][j]);
            u = dp[u][j];
        }
    if (u == v)
        return res;
    for (int j = M; j >= 0; j--)
        if (dp[u][j] != dp[v][j]) {
            res = max({res, sp[u][j], sp[v][j]});
            u = dp[u][j];
            v = dp[v][j];
        }
    return max({res, sp[u][0], sp[v][0]});
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    readInput(N, M, U, V, W);
    checkEdges();
    dfs();
}

int query(int u, int v) {
    int case1 = maxPath(u, v);
    int case2 = min(valC[u], valC[v]);
    int case3 = min(val3[u], val3[v]);
    //cout << u << ' ' << v << ": " << case1 << ' ' << case2 << ' ' << case3 << '\n';
    int res = max(case1, min(case2, case3));
    return (res == INF? -1: res);
}

int getMinimumFuelCapacity(int X, int Y) {
    return query(X + 1, Y + 1);
}

/*int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m), w(m);
    for (int i = 0; i < m; i++)
        cin >> u[i] >> v[i] >> w[i];
    init(n, m, u, v, w);
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << getMinimumFuelCapacity(x, y) << '\n';
    }
    cout.flush();
    return 0;
}*/

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