Submission #299813

#	Time	Username	Problem	Language	Result	Execution time	Memory
299813		jacobtpl	Swapping Cities (APIO20_swap)	C++14	37 / 100	2070 ms	12140 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1100000000
#define sz(x) (int)(x).size()
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ii pair<int,int>

int n,m;
vector<pair<int,ii> > edges;
int p[100005];
int deg[100005];
int maxdeg[100005],deg1[100005];

void init_uf() {
	for (int i=0;i<n;i++) {
		p[i]=i;
		deg[i]=maxdeg[i]=deg1[i]=0;
	}
}
int find(int x) {
	return (p[x]==x)?x:(p[x]=find(p[x]));
}
void join(int x,int y) {
	int a=find(x),b=find(y);
	if (a!=b) {
		maxdeg[b]=max(maxdeg[b],maxdeg[a]);
		deg1[b]+=deg1[a];
		p[a]=b;
	}
}
bool same(int x,int y) {
	return (find(x)==find(y));
}

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++) {
		edges.pb(mp(W[i],mp(U[i],V[i])));
	}
	sort(all(edges));
}

int getMinimumFuelCapacity(int x, int y) {
	init_uf();
	for (auto e:edges) {
		int w=e.first;
		int a=e.second.first;
		int b=e.second.second;

		if (deg[a]==0) deg1[find(a)]++;
		if (deg[a]==1) deg1[find(a)]--;
		deg[a]++;
		maxdeg[find(a)]=max(maxdeg[find(a)],deg[a]);

		if (deg[b]==0) deg1[find(b)]++;
		if (deg[b]==1) deg1[find(b)]--;
		deg[b]++;
		maxdeg[find(b)]=max(maxdeg[find(b)],deg[b]);

		if (!same(a,b)) join(a,b);

		if (same(x,y)) {
			int v=find(x);
			if (maxdeg[v]>2) return w;
			if (maxdeg[v]==2 && deg1[v]==0) 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