Submission #737838

#	Time	Username	Problem	Language	Result	Execution time	Memory
737838		Abrar_Al_Samit	Swapping Cities (APIO20_swap)	C++17	100 / 100	407 ms	51764 KiB

swap

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

const int nax = 2e5 + 3;
const int INF = 2e9;
const int lg = 18;

vector<tuple<int,int,int>>edges;
int n, m;
int nbe[nax/2], lvl[nax/2], tt = 1, st[nax/2], en[nax/2];
vector<pair<int,int>>g[nax/2];
int sz[nax/2], par[nax/2];
int deg[nax];
int sp[nax/2][lg], mxw[nax/2][lg];
bool bam[nax/2];
vector<int>elem[nax];

int find(int v) {
    return par[v] = (v==par[v]) ? v : find(par[v]);
}
bool same(int u, int v) {
    return find(u) == find(v);
}
void unite(int u, int v, int w) {
    int root_u = find(u), root_v = find(v);
    if(sz[root_u] < sz[root_v]) swap(root_u, root_v), swap(u, v);

    if(bam[root_u] && bam[root_v] && deg[u]<2 && deg[v]<2) {
        deg[u]++, deg[v]++;
        par[root_v] = root_u;
        sz[root_u] += sz[root_v];
        bam[root_u] = true;

        for(int x : elem[root_v]) {
            elem[root_u].push_back(x);
        }
        elem[root_v].clear();

    } else {
        if(bam[root_u]) {
            for(int x : elem[root_u]) {
                nbe[x] = w;
            }
        }
        if(bam[root_v]) {
            for(int x : elem[root_v]) {
                nbe[x] = w;
            }
        }

        for(int x : elem[root_v]) {
            elem[root_u].push_back(x);
        }
        elem[root_v].clear();

        par[root_v] = root_u;
        sz[root_u] += sz[root_v];
        bam[root_u] = false;
    }
}
void makeMST() {
    for(int i=0; i<n; ++i) {
        sz[i] = 1, par[i] = i;
        bam[i] = 1;
        elem[i].push_back(i);
    }

    for(auto [w, u, v] : edges) {
        if(same(u, v)) {
            int root = find(u);
            if(bam[root]) {
                for(int x : elem[root]) {
                    nbe[x] = w;
                }
                bam[root] = false;
            }
        } else {
            unite(u, v, w);
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
    }
}   
void dfs(int v, int p = 0, int topar = 0, int lv = 0) {
    lvl[v] = lv;
    sp[v][0] = p;
    mxw[v][0] = topar;
    st[v] = tt++;

    for(int j=1; j<lg; ++j) {
        sp[v][j] = sp[sp[v][j-1]][j-1];
        mxw[v][j] = max(mxw[v][j-1], mxw[sp[v][j-1]][j-1]);
    }

    for(auto [u, w] : g[v]) if(u!=p) {
        dfs(u, v, w, lv+1);
    }
    en[v] = tt-1;
}

bool is_anc(int u, int v) {
    return st[u] <= st[v] && en[u] >= en[v];
}
int get(int u, int v) {
    int ret = 0;
    for(int j=lg-1; j>=0; --j) {
        if(!is_anc(sp[u][j], v)) {
            ret = max(ret, mxw[u][j]);
            u = sp[u][j];
        }
    }   
    if(!is_anc(u, v)) {
        ret = max(ret, mxw[u][0]);
        u = sp[u][0];
    }

    for(int j=lg-1; j>=0; --j) {
        if(!is_anc(sp[v][j], u)) {
            ret = max(ret, mxw[v][j]);
            v = sp[v][j];
        }
    }
    if(!is_anc(v, u)) {
        ret = max(ret, mxw[v][0]);
        v = sp[v][0];
    }
    return ret;
}
void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {

    n = N, m = M;
    for(int i=0; i<M; ++i) {
        edges.emplace_back(W[i], U[i], V[i]);
    }
    for(int i=0; i<N; ++i) {
        nbe[i] = INF;
    }
    sort(edges.begin(), edges.end());

    makeMST();
    dfs(0);
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = max({nbe[X], nbe[Y], get(X, Y)});

    if(ans==INF) ans = -1;
    return ans;
}

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