Submission #1305572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305572		HasanV11010238	Swapping Cities (APIO20_swap)	C++20	100 / 100	308 ms	56744 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define INF 1000000003
#define MAX 200000
#define ll long long
using namespace std;
int n;
vector<vector<int>> v, up;
vector<ll> ans, go, de, pa;
int cur;
struct DSU{
    vector<int> p, le, ri, ro;
    int cmp;
    void init(int n){
        p.assign(n + 1, -1);
        ro.assign(n + 1, 0), le.assign(n + 1, 0), ri.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) ro[i] = i, le[i] = i, ri[i] = i;
        cmp = n;
    }
    int find(int x){
        if (p[x] < 0) return x;
        return p[x] = find(p[x]);
    }
    void merge(int a, int b, ll co){
        int ora = a, orb = b;
        a = find(a), b = find(b);
        if (a == b){
            if (go[ro[a]] == 0) go[ro[a]] = 1, ans[ro[a]] = co;
            return;
        }
        cmp--;
        if (p[a] > p[b]) swap(a, b), swap(ora, orb);
        if (ora == le[a]) swap(le[a], ri[a]);
        if (orb == ri[b]) swap(le[b], ri[b]);
        go[cur] = max(go[ro[a]], go[ro[b]]);
        if (ri[a] != ora || le[b] != orb) go[cur] = 1;
        ri[a] = ri[b];
        ans[cur] = co;
        p[a] += p[b];
        p[b] = a;
        v[cur].push_back(ro[a]);
        v[cur].push_back(ro[b]);
        ro[a] = cur;
        cur++;
    }
};
void dfs(int x, int p){
    //cout<<x<<"\n";
    de[x] = de[p] + 1;
    up[x][0] = p;
    for (int i = 1; i < 20; i++){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    if (go[x] == 0) ans[x] = -1;
    for (auto el : v[x]){
        if (go[x] == 1 && go[el] == 0) ans[el] = ans[x], go[el] = 1;
        dfs(el, x);
    }
}
int dist(int x, int k){
    for (int i = 0; i < 20; i++){
        int val = (k & (1<<i));
        if (val != 0){
            x = up[x][i];
        }
    }
    return x;
}
int lca(int a, int b){
    if (de[a] > de[b]) swap(a, b);
    b = dist(b, de[b] - de[a]);
    if (a == b) return a;
    for (int i = 19; i >= 0; i--){
        if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    }
    return up[a][0];
}
DSU ds;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    v.assign(2 * n + 1, vector<int>()), ans.assign(2 * n + 1, INF), go.assign(2 * n + 1, 0);
    de.assign(2 * n + 1, 0), pa.assign(2 * n + 1, 0), cur = n + 1;
    up.assign(2 * n + 1, vector<int>(20, 0));
    vector<vector<int>> so;
    for (int i = 0; i < M; i++){
        so.push_back({W[i], U[i] + 1, V[i] + 1});
    }
    ds.init(n);
    sort(so.begin(), so.end());
    for (auto el : so){
        ds.merge(el[1], el[2], el[0]);
    }
    for (int i = 1; i <= 2 * n - 1; i++){
        /*cout<<go[i]<<" "<<i<<": ";
        for (auto el : v[i]) cout<<el<<" ";
        cout<<"\n";*/
    }
    dfs(cur - 1, 0);
}
int getMinimumFuelCapacity(int x, int y){
    x++, y++;
    return ans[lca(x, y)];
}

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