Submission #982652

#	Time	Username	Problem	Language	Result	Execution time	Memory
982652		dimashhh	Swapping Cities (APIO20_swap)	C++17	100 / 100	271 ms	60488 KiB

swap

#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+12;

vector<pair<int,int>> g[N];
vector<int> gr[N],st[N];
int n,m,p[N],timer=0,t[N],e1[N],e2[N],first_time[N];
bool is[N];
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
int n1,tt[N],P[N];
void merge(int a,int b){
    int vv,uu;
    vv = a;
    uu = b;
    a = get(a);
    b = get(b);
    if(a == b){
        if(!is[a]){
            for(int j:st[a]){
                first_time[j]=timer;
            }
            st[a].clear();
            is[a]=1;
        }
        timer++;
        return;
    }
    if((int)st[a].size() > (int)st[b].size()){
        swap(vv,uu);
        swap(a, b);
    }
    n1++;
    tt[n1] = timer;
//    cout << n1 << ' ' << P[a] << ' ' << P[b] << "x\n";
    gr[n1].push_back(P[a]);
    gr[n1].push_back(P[b]);
    P[b] = n1;
    p[a] = b;
    for(int j:st[a]){
        st[b].push_back(j);
    }
    st[a].clear();
    if(is[b] || is[a] || (vv != e1[a] && vv != e2[a]) || (uu != e1[b] && uu != e2[b])) {
        is[b]=1;
        for(int j:st[b]){
            first_time[j]=timer;
        }
        st[b].clear();
    }else{
        if(uu == e1[b]){
            e1[b] = (vv == e1[a] ? e2[a] : e1[a]);
        }else{
            e2[b] = (vv == e1[a] ? e2[a] : e1[a]);
        }
    }
    timer++;
}
int B = 20;
int up[N][20],tin[N],tout[N],tv;
void dfs(int v,int pr){
    up[v][0] = pr;
    tin[v] = tv++;
    for(int i = 1;i < B;i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:gr[v]){
        dfs(to,v);
    }
    tout[v] = tv++;
}
bool is_pr(int a,int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int v,int u){
    if(is_pr(v,u)) return v;
    if(is_pr(u,v)) return u;
    for(int i = B - 1;i >= 0;i--){
        if(!is_pr(up[v][i],u)){
            v = up[v][i];
        }
    }
    return up[v][0];
}
vector <array<int, 3>> e;
void init(int nn, int mm,std::vector<int> u, std::vector<int> v, std::vector<int> w) {
    memset(first_time,-1,sizeof(first_time));
    n1 = n = nn;
    m = mm;
    for (int i = 1; i <= m; i++) {
        e.push_back({w[i - 1], u[i - 1] + 1, v[i - 1] + 1});
    }
    sort(e.begin(), e.end());
    for(int i = 1;i <= n;i++) {
        P[i] =e1[i] = e2[i] = p[i] = i;
        st[i].push_back(i);
    }
    for(auto [w,a,b]:e){
        merge(a,b);
    }
    dfs(n1,n1);
}
void merge1(int a,int b){
    a = get(a);
    b = get(b);
    p[a] = b;
}
int getMinimumFuelCapacity(int X, int Y) {
    X++;Y++;
    int f = max(first_time[X],max(tt[lca(X,Y)],first_time[Y]));
    if(first_time[X] == -1 || first_time[Y] == -1) return -1;
    return e[f][0];
}

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