Submission #1175769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175769		Muhammet	Swapping Cities (APIO20_swap)	C++17	100 / 100	274 ms	84048 KiB

swap

#include "bits/stdc++.h"
#include "swap.h"
// #include "grader.cpp"

using namespace std;

#define ff first
#define ss second

const int N = 6e5 + 5;

int p[N], a[N], c[N], h[N], par[N], sp[N][35];

pair <int, int> r[N];

vector <int> v[N];

int fnd(int x) {
    if(p[x] == x) return x;
    return p[x] = fnd(p[x]);
}

void dfs(int x, int y) {
    h[x] = h[y] + 1;
    par[x] = y;
    for(auto i : v[x]) {
        dfs(i, x);
    }
}

int lca(int x, int y) {
    if(h[x] < h[y]) swap(x, y);
    for(int i = 29; i >= 0; i--) {
        if(h[sp[x][i]] >= h[y]) x = sp[x][i];
    }
    if(x == y) return x;
    for(int i = 29; i >= 0; i--) {
        if(sp[x][i] != sp[y][i]) x = sp[x][i], y = sp[y][i];
    }
    return par[x];
}

void init(int n, int m, vector<int> U1, vector<int> U2, vector<int> W) {
    vector <pair <int, pair <int, int>>> v1;
    for(int i = 0; i < m; i++) {
        v1.push_back({W[i], {U1[i]+1, U2[i]+1}});
    }
    sort(v1.begin(), v1.end());
    for(int i = 0; i <= 2 * (n + m); i++) {
        p[i] = i;
        r[i] = {i, i};
    }
    int u3 = n;
    for(auto [w, u] : v1) {
        auto [u1, u2] = u;
        u1 = fnd(u1), u2 = fnd(u2);
        u3++;
        p[u1] = p[u2] = u3;
        c[u3] = w;
        if(u1 != u2) {
            if(a[u1] or a[u2]) a[u3] = true;
            else {
                if((u.ff == r[u1].ff or u.ff == r[u1].ss) and (u.ss == r[u2].ff or u.ss == r[u2].ss)) {
                    if(u.ff == r[u1].ff) r[u3].ff = r[u1].ss;
                    else r[u3].ff = r[u1].ff;
                    if(u.ss == r[u2].ff) r[u3].ss = r[u2].ss;
                    else r[u3].ss = r[u2].ff;
                }
                else a[u3] = true;
            }
            v[u3].push_back(u1);
            v[u3].push_back(u2);
        }
        else {
            a[u3] = true;
            v[u3].push_back(u1);
        }
    }
    dfs(u3, 0);
    for(int i = 0; i <= u3; i++) {
        sp[i][0] = par[i];
    }
    for(int j = 1; j < 30; j++) {
        for(int i = 0; i <= u3; i++) {
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }
    a[0] = 1;
    c[0] = -1;
    return;
}

int getMinimumFuelCapacity(int x, int y) {
    int z = lca(x+1, y+1);
    if(a[z]) return c[z];
    for(int i = 29; i >= 0; i--) {
        if(!a[sp[z][i]]) z = sp[z][i];
    }
    return c[par[z]];
}

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