Submission #1088348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088348		modwwe	Swapping Cities (APIO20_swap)	C++17	100 / 100	116 ms	15188 KiB

swap

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int inf = 2e9;
const int maxn = 2e5+5;
int a[maxn],c[maxn],d[maxn],p[maxn];

int findpar(int u){
    return (p[u]<0?u:findpar(p[u]));
}
void unions(int u,int v,int w,bool e){
    u=findpar(u);v=findpar(v);
    if(u==v) c[u]=min(c[u],w);
    else{
        if(p[u]>p[v]) swap(u,v);
        p[u]+=p[v];p[v]=u;a[v]=w;
        c[u]=min(c[u],max(w,e?0:c[v]));
    }
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    for(int i=0;i<N;i++) p[i]=-1,a[i]=c[i]=inf;
    vector<int> ord(M);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int x,int y){
        return W[x]<W[y];
    });
    for(int i:ord){
        d[U[i]]++;d[V[i]]++;
        unions(U[i],V[i],W[i],(d[U[i]]>=3 || d[V[i]]>=3));
    }
}

int getMinimumFuelCapacity(int u, int v) {
    int w=-1;
    while(u!=v){
        if(a[u]<a[v]) w=a[u],u=p[u];
        else w=a[v],v=p[v];
    }
    while(u>=0){
        if(c[u]!=inf) return max(w,c[u]);
        w=a[u];u=p[u];
    }
    return -1;
}

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