Submission #367768

#	Time	Username	Problem	Language	Result	Execution time	Memory
367768		Sara	Swapping Cities (APIO20_swap)	C++14	100 / 100	481 ms	50728 KiB

swap

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back

const int O = 3e5 + 5;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll  inf = 1e9 + 5;

int n, m, q, par[O];
int deg[O];
int mn1[O], mn2[O];
int h[O], pr[LOG][O];
vector <int> g[O];

struct edge{
    int u = 0, v = 0, w = 0, id = 0;
} e[O];

bool cmp(edge e1, edge e2){
    return make_pair(e1.w, e1.id) < make_pair(e2.w, e2.id);
}

void clear(){
    for (int v = 1; v < O; v ++){
        par[v] = v;
        mn1[v] = mn2[v] = inf;
    }
    return;
}

int find_par(int v){
    if (par[v] == v) return v;
    return par[v] = find_par(par[v]);
}

void merge(int u, int v, int w){
    deg[u] ++; deg[v] ++;
    int pu = find_par(u);
    int pv = find_par(v);
    if (pu == pv){
        mn2[pv] = min(mn2[pv], w);
    }
    else {
        n ++;
        mn1[n] = w;
        mn2[n] = min(mn2[pu], mn2[pv]);
        par[pu] = par[pv] = n;
        g[n].pb(pu); g[n].pb(pv);
        pr[0][pu] = pr[0][pv] = n;
        if (3 <= deg[u] || 3 <= deg[v]){
            mn2[n] = min(mn2[n], w);
        }
    }
    return;
}

void dfs(int v){
    for (int u : g[v]){
        h[u] = h[v] + 1;
        dfs(u);
    }
    return;
}

void build(){
    for (int i = 1; i < LOG; i ++){
        for (int v = 1; v <= n; v ++){
            pr[i][v] = pr[i - 1][pr[i - 1][v]];
        }
    }
    return;
}

int get_par(int v, int dif){
    for (int i = 0; i < LOG; i ++){
        if ((dif >> i) & 1){
            v = pr[i][v];
        }
    }
    return v;
}

int LCA(int u, int v){
    if (h[v] < h[u]) swap(u, v);
    v = get_par(v, h[v] - h[u]);
    if (u == v) return v;
    for (int i = LOG - 1; i >= 0; i --){
        if (pr[i][u] != pr[i][v]){
            u = pr[i][u];
            v = pr[i][v];
        }
    }
    v = pr[0][v];
    return v;
}

int getMinimumFuelCapacity(int X, int Y){
    X ++; Y ++;
    int lca = LCA(X, Y);
    if (mn2[lca] != inf){
        return max(mn1[lca], mn2[lca]);
    }
    for (int i = LOG - 1; i >= 0; i --){
        int up = pr[i][lca];
        if (up && mn2[up] == inf){
            lca = up;
        }
    }
    lca = pr[0][lca];
    if (lca == 0) return -1;
    return max(mn1[lca], mn2[lca]);
}

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 ++){
        e[i].u = U[i] + 1;
        e[i].v = V[i] + 1;
        e[i].w = W[i];
        e[i].id = i;
    }
    sort(e, e + M, cmp);
    clear();
    for (int i = 0; i < m; i ++){
        merge(e[i].u, e[i].v, e[i].w);
    }    
    dfs(n); build();
    return;
}

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