Submission #1303988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303988		vtnoo	Swapping Cities (APIO20_swap)	C++20	37 / 100	2094 ms	8264 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int n,m;
struct Edge{
	int a,b,c;
	bool operator<(const Edge&o)const{
		return c<o.c;
	}
};
int lin[MAXN],tam[MAXN],deg[MAXN];
bool info[MAXN];
int find(int x){
	while(lin[x]!=x)x=lin[x];
	return x;
}
void dsu(int a,int b){
	a=find(a),b=find(b);
	if(a==b){
		info[a]=true;
		return;
	}
	if(tam[a]<tam[b])swap(a,b);
	tam[a]+=tam[b];
	lin[b]=a;
	info[a]=info[a]|info[b];
}
vector<Edge>e;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N,m=M;
    fore(i,0,m){
		e.pb(Edge{U[i],V[i],W[i]});
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	fore(i,0,n){
		lin[i]=i;
		tam[i]=1;
		deg[i]=0;
		info[i]=false;
	}
	sort(ALL(e));
	fore(i,0,m){
		dsu(e[i].a,e[i].b);
		deg[e[i].a]++;
		deg[e[i].b]++;
		if(deg[e[i].a]>=3||deg[e[i].b]>=3){
			info[find(e[i].a)]=true;
		}
		if(find(X)==find(Y)&&info[find(X)]){
			return e[i].c;
		}
	}
	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