Submission #676527

#	Time	Username	Problem	Language	Result	Execution time	Memory
676527		fatemetmhr	Swapping Cities (APIO20_swap)	C++17	100 / 100	335 ms	57060 KiB

swap

// ~~ Be name khoda ~~

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 3e5 + 10;
const int lg    = 21;


int parlca[lg][maxn5], par[maxn5], len[maxn5];
int h[maxn5], ans[maxn5], sar[maxn5], tah[maxn5];
bool masir[maxn5], allno = false;
vector <int> adj[maxn5];
vector <pair<int, int>> ed;


int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}

void dfs(int v){
    if(!masir[v])
        ans[v] = len[v];
    for(int i = 1; i < lg && parlca[i - 1][v] != -1; i++)
        parlca[i][v] = parlca[i - 1][parlca[i - 1][v]];
    for(auto u : adj[v]){
        ans[u] = ans[v];
        parlca[0][u] = v;
        h[u] = h[v] + 1;
        dfs(u);
    }
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = parlca[i][a];
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(parlca[i][a] != parlca[i][b]){
        a = parlca[i][a];
        b = parlca[i][b];
    }
    return parlca[0][a];
}

void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    for(int i = 0; i < m; i++)
        ed.pb({W[i], i});
    sort(all(ed));
    memset(par, -1, sizeof par);
    int newnode = n;
    memset(masir, true, sizeof masir);
    for(int i = 0; i < n; i++)
        sar[i] = tah[i] = i;
    for(auto [w, id] : ed){
        int u = get_par(U[id]), v = get_par(V[id]);
        //cout << "ok " << u << ' ' << v << ' ' << U[id] << ' ' << V[id] << ' ' << w << endl;
        if(u == v){
            if(masir[u]){
                masir[u] = false;
                len[u] = w;
            }
            continue;
        }
        par[u] = newnode;
        par[v] = newnode;
        len[newnode] = w;
        masir[newnode] = (masir[u] && masir[v]);
        if(masir[newnode]){
            bool re1 = U[id] == sar[u] || U[id] == tah[u];
            bool re2 = V[id] == sar[v] || V[id] == tah[v];
            masir[newnode] = re1 && re2;
            if(masir[newnode]){
                sar[newnode] = U[id] == sar[u] ? tah[u] : sar[u];
                tah[newnode] = V[id] == sar[v] ? tah[v] : sar[v];
            }
        }
        adj[newnode].pb(u);
        adj[newnode].pb(v);
        //cout << "ya merged " << newnode << ' ' << masir[newnode] << ' ' << sar[newnode] << ' ' << tah[newnode] << endl;
        newnode++;
    }
    if(masir[newnode - 1]){
        allno = true;
        return;
    }
    memset(parlca, -1, sizeof parlca);
    dfs(newnode - 1);
}

int getMinimumFuelCapacity(int x, int y){
    if(allno)
        return -1;
    int c = lca(x, y);
    return max({len[c], ans[x], ans[y]});
}

// hen?

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