Submission #1164312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164312		Otalp	Swapping Cities (APIO20_swap)	C++20	100 / 100	269 ms	57164 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

vector<pii> q[200100];
int pos[200100];
vector<int> h;
int n, m, timer=0;
int p[200100], sz[200100];
int bcl[200100];
int dsz[200100];
int jmp[100100][20], mx[100100][20];
vector<int> d[200100];
int tin[200100], tout[200100];


int get(int a){
    if(p[a] == a) return a;
    return p[a] = get(p[a]);
}

void un(int a, int b, int cl){
    int ok = 0;
    if(bcl[get(a)] != 0 or bcl[get(b)] != 0) ok = 1;
    dsz[a] ++;
    dsz[b] ++;
    if(dsz[b] > 2 or dsz[a] > 2) ok = 1;
    if(get(a) == get(b)) ok = 1;
    a = get(a);
    b = get(b);
    if(a == b){
        // cout<<"ASDasdasd\n";
        while(d[a].size()){
            // cout<<a<<'\n';
            bcl[d[a].back()] = cl;
            d[a].pop_back();
        }
        return;
    }
    if(sz[a] < sz[b]) swap(a, b);
    if(ok){
        while(d[a].size()){
            bcl[d[a].back()] = cl;
            d[a].pop_back();
        }
        while(d[b].size()){
            bcl[d[b].back()] = cl;
            d[b].pop_back();
        }
    }
    while(d[b].size()){
        d[a].pb(d[b].back());
        d[b].pop_back();
    }
    p[b] = a;
    sz[a] += sz[b];
}

void dfs(int v, int p){
    // pos[v] = 1;
    tin[v] = ++timer;
    for(pii g: q[v]){
        int to = g.ff;
        int e = g.ss;
        if(to == p) continue;
        jmp[to][0] = v;
        mx[to][0] = e;
        dfs(to, v);
    }
    tout[v] = ++ timer; 
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] and tout[a] >= tout[b]);
}

int lca(int a, int b){
    if(upper(a, b)){
        int res = 0;
        for(int i = 17; i>=0; i--){
            if(upper(jmp[b][i], a)) continue;
            res = max(res, mx[b][i]);
            b = jmp[b][i];
        }
        res = max(res, mx[b][0]);
        return res;
    }
    if(upper(b, a)){
        // cout<<a<<' '<<b<<'\n';
        int res = 0;
        for(int i = 17; i>=0; i--){
            if(upper(jmp[a][i], b)) continue;
            res = max(res, mx[a][i]);
            a = jmp[a][i];
        }
        res = max(res, mx[a][0]);
        return res;
    }
    int res = 0;
    for(int i = 17; i>=0; i--){
        if(upper(jmp[b][i], a)) continue;
        res = max(res, mx[b][i]);
        b = jmp[b][i];
    }
    for(int i = 17; i>=0; i--){
        if(upper(jmp[a][i], b)) continue;
        res = max(res, mx[a][i]);
        a = jmp[a][i];
    }
    res = max(res, mx[a][0]);
    res = max(res, mx[b][0]);
    return res;
}

// bool check(int k, int x, int y){
//     int mn = 
// }

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N, m = M;
    vector<vector<int> > dh;
    for(int i=0; i<m; i++){
        int l = U[i], r = V[i], x = W[i];
        dh.pb({x, l, r});
    }
    for(int i=0; i<n; i++){
        sz[i] = 1;
        p[i] = i;
        d[i].pb(i);
    }
    sort(dh.begin(), dh.end());
    for(auto g: dh){
        int x = g[0], l = g[1], r = g[2];
        if(get(l) != get(r)){
            q[l].pb({r, x});
            q[r].pb({l, x});
        }
        un(l, r, x);
    }
    // for(int i=0; i<n; i++) cout<<bcl[i]<<' ';
    dfs(0, -1);
    for(int k=1; k<=17; k++){
        for(int i=1; i<=n; i++){
            jmp[i][k] = jmp[jmp[i][k-1]][k-1];
            mx[i][k] = max(mx[i][k-1], mx[jmp[i][k-1]][k-1]);
        }
    }
}


int getMinimumFuelCapacity(int X, int Y) {
    // int l=1, r=1e9 + 1;
    // if(!check(r, X, Y)) return -1;
    // while(l < r){
    //     int mid = (l + r)/2;
    //     if(check(mid, X, Y)) r = mid;
    //     else l = mid + 1;
    // }
    if(bcl[X] == 0 or bcl[Y] == 0) return -1;
    int mx = max(bcl[X], bcl[Y]);
    mx = max(mx, lca(X, Y));
    return mx;
}

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