Submission #1030187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030187		vjudge1	Swapping Cities (APIO20_swap)	C++17	37 / 100	2041 ms	12228 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
vector<tuple<int,int,int>> edg;
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W) {
    for(int i=0;i<M;i++)
        edg.push_back({W[i],++U[i],++V[i]});
    sort(edg.begin(),edg.end());
}
int par[100100],deg[100100];
bitset<100100>yes;
int abp(int n){
    return par[n]?par[n]=abp(par[n]):n;
}
int getMinimumFuelCapacity(int X,int Y) {
    yes.reset(); ++X,++Y;
    memset(par,0,sizeof par);
    memset(deg,0,sizeof deg);
    for(auto[w,u,v]:edg){
        deg[u]++,deg[v]++;
        if(deg[u]>2)
            yes[abp(v)]=1;
        if(deg[v]>2)
            yes[abp(v)]=1;
        u=abp(u),v=abp(v);
        if(u-v) par[u]=v,
            yes[v]=yes[v]|yes[u];
        else yes[v]=1;
        if(abp(X)==abp(Y)&&yes[abp(X)])
            return w;
    }
    return -1;
}

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