Submission #437532

#	Time	Username	Problem	Language	Result	Execution time	Memory
437532		Sohsoh84	Swapping Cities (APIO20_swap)	C++14	100 / 100	450 ms	81952 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

int n, m, P[MAXN], H[MAXN], deg[MAXN], E[MAXN];
vector<int> C[MAXN];
vector<pll> par[MAXN];
vector<pair<ll, pll>> edges;

inline void Union(int v, int u, int ind) {
	deg[v]++;
	deg[u]++;
	bool B = (deg[v] > 2 || deg[u] > 2);
	
	v = P[v], u = P[u];
	if (v == u) {
		E[v]++;
		if ((B || E[v] >= C[v].size()) && H[v] < 0)
			for (int e : C[v])
				H[e] = ind;
		return;
	}
	
	if (C[v].size() > C[u].size()) swap(v, u);
	
	E[u] += E[v] + 1;
	B |= (E[u] >= C[u].size() + C[v].size());
	B |= (H[v] >= 0 || H[u] >= 0);
	
	if (B) {
		if (H[v] < 0)
			for (int e : C[v])
				H[e] = ind;
		if (H[u] < 0)
			for (int e : C[u])
				H[e] = ind;
	}

	for (int e : C[v]) {
		C[u].push_back(e);
		par[e].push_back({ind, u});
		P[e] = u;
	}

	C[v].clear();
}

inline int Par(int v, int t) {
	auto it = lower_bound(all(par[v]), make_pair(t + 1, -1));
	it--;
	return it -> Y;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N, m = M;
	for (int i = 1; i <= n; i++) {
		P[i] = i; 
		C[i].push_back(i); 
		par[i].push_back({-1, i});
		H[i] = -1;
	}

	for (int i = 0; i < m; i++) {
		int v = V[i] + 1, u = U[i] + 1, w = W[i];
		edges.push_back({w, {v, u}});
	}

	sort(all(edges));
	for (int i = 0; i < m; i++)
		Union(edges[i].Y.X, edges[i].Y.Y, i);
}

int getMinimumFuelCapacity(int u, int v) {
	u++;
	v++;
 	if (H[u] < 0 || H[v] < 0 || P[v] != P[u]) return -1;
	
	int L = 0, R = m - 1;
	while (L < R) {
		int mid = (L + R) >> 1;
		if (H[u] <= mid && H[v] <= mid && Par(v, mid) == Par(u, mid)) R = mid;
		else L = mid + 1;
	}
	
	return edges[L].X;
}

Compilation message (stderr)

swap.cpp: In function 'void Union(int, int, int)':
swap.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if ((B || E[v] >= C[v].size()) && H[v] < 0)
      |             ~~~~~^~~~~~~~~~~~~~
swap.cpp:42:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  B |= (E[u] >= C[u].size() + C[v].size());
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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