Submission #698952

#	Time	Username	Problem	Language	Result	Execution time	Memory
698952		Cross_Ratio	Swapping Cities (APIO20_swap)	C++14	7 / 100	264 ms	36548 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
array<int, 3> Edge[200005];
vector<int> adj[200005];
int cnt = 0;
int ans[200005];
int N, M;
struct UnionFind {
    vector<int> root;
    vector<int> L, R, V;
    UnionFind(int N) {
        root.resize(N);
        L.resize(N);
        R.resize(N);
        V.resize(N);
        for(int i = 0; i<N;i++) {
            root[i] = -1;
            L[i] = R[i] = V[i] = i;
        }
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int a, int b, int d) {
       int x = Find(a), y = Find(b);
        if(x==y) {
            ans[V[x]] = min(ans[V[x]], d);
            return;
        }
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
        bool isLine = true;
        if(a==L[x]) {
            int k = L[x];
            L[x] = R[x];
            R[x] = k;
        }
        if(a != R[x]) isLine = false;
        if(b == R[y]) {
            int k = L[y];
            L[y] = R[y];
            R[y] = k;
        }
        if(b != L[y]) isLine = false;
        if(!isLine) {
            ans[V[x]] = min(ans[V[x]], d);
            ans[V[y]] = min(ans[V[y]], d);
        }
        ans[cnt] = min(ans[V[x]], ans[V[y]]);
        ans[cnt] = max(ans[cnt], d);
        if(ans[cnt]!=INF) isLine = false;
        R[x] = R[y];
        adj[cnt].push_back(V[x]);
        adj[cnt].push_back(V[y]);
        V[x] = cnt;
        cnt++;
    }
};
int par[200005][20];
int dep[200005];
void dfs(int c, int p, int d, int k) {
    k = min(k, ans[c]);
    ans[c] = k;
    par[c][0] = p;
    dep[c] = d;
    for(int n : adj[c]) {
        dfs(n, c, d+1, k);
    }
}
int LCA(int x, int y) {
    if(dep[x]<dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    int i;
    for(i=19;i>=0;i--) {
        if(d&(1<<i)) x = par[x][i];
    }
    if(x==y) return x;
    for(i=19;i>=0;i--) {
        if(par[x][i]!=par[y][i]) {
            x = par[x][i], y = par[y][i];
        }
    }
    assert(par[x][0]==par[y][0]);
    return par[x][0];
}
void init(int _N, int _M,vector<int> _U, vector<int> _V, vector<int> _W) {
    N = _N, M = _M;
    int i, j;
    for(i=0;i<M;i++) Edge[i] = {_W[i], _U[i], _V[i]};
    cnt = N;
    for(i=0;i<=2*N;i++) ans[i] = INF;
    sort(Edge, Edge+M);
    UnionFind UF(N);
    for(i=0;i<M;i++) {
        UF.Merge(Edge[i][1], Edge[i][2], Edge[i][0]);
    }
    dfs(cnt-1, cnt, 0, INF);
    par[cnt][0] = cnt;
    /*for(i=0;i<=cnt;i++) {
        cout << par[i][0] << ' ';
    }
    cout << '\n';
    for(i=0;i<=cnt;i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';*/
    for(j=1;j<20;j++) {
        for(i=0;i<=cnt;i++) {
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    int v = ans[LCA(X, Y)];
    //cout << X << ' ' << Y << ' ' << LCA(X, Y) << '\n';
    return (v==INF?-1:v);
}

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