Submission #645196

#	Time	Username	Problem	Language	Result	Execution time	Memory
645196		dooompy	Swapping Cities (APIO20_swap)	C++17	0 / 100	544 ms	44516 KiB

swap

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<climits>
#include"swap.h"
#define ff first
#define ss second
using namespace std;
int n, m;
vector<pair<int, pair<int, int>>> edges;
vector<vector<int>> binlift;
vector<int> depths;
vector<int> swapp;
 
int getp(int x, vector<int>& dsu) {
	if (dsu[x] == x)return x;
	return dsu[x] = getp(dsu[x], dsu);
}
void merge(int a, int b, int x, vector<int>& 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 (int i = 0; i < m; i++) {
		edges.push_back({ W[i], {U[i], V[i]} });
	}
	sort(edges.begin(), edges.end());
	vector<int> dsu(n + m);
	for (int i = 0; i < n + m; i++)dsu[i] = i;
	swapp.assign(n + m, INT_MAX);
	vector<vector<int>>child(n + m);
	vector<int>deg(n, 0);
	binlift.assign(n + m, vector<int>(20, -1));
	for (int i = 0; i < m; i++) {
		int a = edges[i].ss.ff;
		int b = edges[i].ss.ss;
		int oa = a;
		int 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] != INT_MAX || swapp[b] != INT_MAX || (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 (int i = n + m - 1; i >= 0; i--) {
		for (int j = 0; j < child[i].size(); j++) {
			depths[child[i][j]] = depths[i] + 1;
		}
	}
	for (int i = n + m - 1; i >= 0; i--) {
		int 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]) {
		int tmp = X;
		X = Y;
		Y = tmp;
	}
	while (depths[X] != depths[Y]) {
		X = binlift[X][floor(log2(depths[X] - depths[Y]))];
	}
	while (X != Y) {
		int i = 19;
		while (binlift[X][i] == binlift[Y][i] && i > 0)i--;
		X = binlift[X][i];
		Y = binlift[Y][i];
	}
	return swapp[X] == INT_MAX ? -1 : swapp[X];
}

Compilation message (stderr)

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

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