제출 #617991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
617991		GlassesNerd	Swapping Cities (APIO20_swap)	C++17	6 / 100	599 ms	64112 KiB

swap

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<climits>
#include"swap.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n, m;
vector<pair<ll, pair<ll, ll>>> edges;
vector<vector<ll>> binlift;
vector<ll> depths;
vector<ll> swapp;

ll getp(ll x, vector<ll>& dsu) {
	if (dsu[x] == x)return x;
	return dsu[x] = getp(dsu[x], dsu);
}
void merge(ll a, ll b, ll x, vector<ll>& dsu) {
	a = getp(a, dsu);
	b = getp(b, dsu);
	dsu[a] = x;
	dsu[b] = x;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	m = M;
	for (ll i = 0; i < m; i++) {
		edges.push_back({ W[i], {U[i], V[i]} });
	}
	sort(edges.begin(), edges.end());
	vector<ll> dsu(n + m);
	for (ll i = 0; i < n + m; i++)dsu[i] = i;
	swapp.assign(n + m, LLONG_MAX / 2);
	vector<vector<ll>>child(n + m);
	vector<ll>deg(n, 0);
	binlift.assign(n + m, vector<ll>(20, -1));
	for (ll i = 0; i < m; i++) {
		ll a = edges[i].ss.ff;
		ll b = edges[i].ss.ss;
		ll oa = a;
		ll ob = b;
		a = getp(a, dsu);
		b = getp(b, dsu);
		if (a != b) {
			merge(a, b, i + n, dsu);
			binlift[a][0] = i + n;
			binlift[b][0] = i + n;
			if (swapp[a] != LLONG_MAX / 2 || swapp[b] != LLONG_MAX / 2 || (deg[oa] >= 2 && deg[ob] >= 2)) {
				swapp[i + n] = edges[i].ff;
			}
			child[i + n].push_back(a);
			child[i + n].push_back(b);
		}
		else {
			swapp[a] = min(swapp[a], edges[i].ff);
		}
		deg[oa]++;
		deg[ob]++;
	}
	depths.assign(n + m, 0);
	for (ll i = n + m - 1; i >= 0; i--) {
		for (ll j = 0; j < child[i].size(); j++) {
			depths[child[i][j]] = depths[i] + 1;
			swapp[child[i][j]] = min(swapp[child[i][j]], swapp[i]);
		}
	}
	for (ll i = n + m - 1; i >= 0; i--) {
		ll j = 0;
		while (binlift[i][j] != -1) {
			binlift[i][j + 1] = binlift[binlift[i][j]][j];
			j++;
		}
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	if (depths[X] < depths[Y]) {
		ll tmp = X;
		X = Y;
		Y = tmp;
	}
	while (depths[X] != depths[Y]) {
		X = binlift[X][floor(log2(depths[X] - depths[Y]))];
	}
	while (X != Y) {
		ll i = 19;
		while (binlift[X][i] == binlift[Y][i] && i > 0)i--;
		X = binlift[X][i];
		Y = binlift[Y][i];
	}
	return swapp[X] == LLONG_MAX / 2 ? -1 : swapp[Y];
}
/*signed main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> U(M), V(M), W(M);
	for (ll i = 0; i < M; i++)cin >> U[i] >> V[i] >> W[i];
	init(N, M, U, V, W);
	ll Q;
	cin >> Q;
	while (Q--) {
		ll a, b;
		cin >> a >> b;
		cout << getMinimumFuelCapacity(a, b) << "\n";
	}
}*/

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:65:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (ll j = 0; j < child[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~~~

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