Submission #308158

#	Time	Username	Problem	Language	Result	Execution time	Memory
308158		fefe	Swapping Cities (APIO20_swap)	C++17	100 / 100	481 ms	19432 KiB

swap

#include "swap.h"

#include <vector>
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAX_N = 100005;

struct EDGE{
	int x,y;
	int v;
	EDGE(int _x, int _y, int _v): x(_x), y(_y), v(_v){}
};
vector<EDGE> lst;
vector<pair<int, bool> > num[MAX_N];
int par[MAX_N], height[MAX_N];
int deg[MAX_N];
int val[MAX_N];
int m;

int find_par(int x, int max_val){
	if(val[x] > max_val){	
		return x;
	}
	if(x == par[x])	return x;
	return find_par(par[x], max_val);
}
void merge(int x, int y, int v){
	deg[x]++;
	deg[y]++;
	bool Z = false;
	if(deg[x] == 3 || deg[y] == 3)	Z = true;
	
	x = find_par(x, v);
	y = find_par(y, v);
	if(x == y){
		num[x].push_back(pair<int, bool>(v, true));
		return;
	}
	if(height[y] > height[x]){
		swap(x,y);
	}
	par[y] = x;
	val[y] = v;
	height[x] += height[x] == height[y];
	Z |= num[x].back().se | num[y].back().se;
	num[x].push_back(pair<int, bool>(v, Z));
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	m = M;
	for(int i=0;i<M;i++){
		lst.push_back(EDGE(U[i], V[i], W[i]));
	}
	
	for(int i=0;i<N;i++){
		par[i] = i;
		height[i] = 1;
		deg[i] = 0;
		val[i] = -1;
		num[i].push_back(pair<int, bool>(-1, 0));
	}

	sort(lst.begin(), lst.end(), [&](const EDGE x, const EDGE y){
		return x.v < y.v;
	});
	
	int i = 0;
	for(EDGE p:lst){
		merge(p.x, p.y, i);
		i++;
	}
}

bool is_ok(int max_val, int x, int y){
	x = find_par(x, max_val);
	y = find_par(y, max_val);
	
	if(x != y)	return false;
	
	int idx = lower_bound(num[x].begin(), num[x].end(), pair<int, bool>(max_val + 1, false)) - num[x].begin() - 1;
	return num[x][idx].se;
}

int getMinimumFuelCapacity(int X, int Y) {
	int l = 0, r = m-1;
	while(l < r){
		int mid = (l + r) >> 1;
		if(is_ok(mid, X, Y)){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	return is_ok(l, X, Y) ? lst[l].v : -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