Submission #308104

#	Time	Username	Problem	Language	Result	Execution time	Memory
308104		fefe	자매 도시 (APIO20_swap)	C++17	13 / 100	376 ms	20436 KiB

swap

#include "swap.h"

#include <vector>
#include<bits/stdc++.h>
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){}
	bool operator < (const EDGE d){
		if(v == d.v){
			return x < d.x;
		}
		return v < d.v;
	}
};
vector<EDGE> lst, cnt[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;
	return (x == par[x]) ? (x) : (par[x] = find_par(par[x], max_val));
}
void merge(int x, int y, int v){
	deg[x]++;
	deg[y]++;
	x = find_par(x, v);
	y = find_par(y, v);
	if(x == y){
		EDGE p = cnt[x].back();
		p.y++;
		p.v = v;
		if(deg[x] == 3 || deg[y] == 3)	p.y++;
		cnt[x].push_back(p);
		return;
	}
	if(height[y] > height[x]){
		swap(x,y);
	}
	par[y] = x;
	val[y] = v;
	height[x] += height[x] == height[y];

	EDGE p = EDGE(cnt[x].back().x + cnt[y].back().x, cnt[x].back().y + cnt[y].back().y + 1, v);
	if(deg[x] == 3 || deg[y] == 3)	p.y++;
	cnt[x].push_back(p);
}
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;
		val[i] = -1;
		cnt[i].push_back(EDGE(1,0,-1));
	}

	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(cnt[x].begin(), cnt[x].end(), EDGE(MAX_N, MAX_N, max_val)) - cnt[x].begin() - 1;

	return cnt[x][idx].x <= cnt[x][idx].y;
}

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: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27