Submission #396474

#	Time	Username	Problem	Language	Result	Execution time	Memory
396474		Kevin_Zhang_TW	Swapping Cities (APIO20_swap)	C++17	100 / 100	556 ms	23108 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9 + 7;

int ok_t[MAX_N], wei[MAX_N];

struct dsu {
	vector<int> sz, good, deg;
	vector<vector<pair<int,int>>> g;
	dsu(int n = 0) { 
		g.resize(n), sz.resize(n, 1), good.resize(n), deg.resize(n);
		for (int i = 0;i < n;++i)
			g[i] = {{-1, i}};
	}
	// I want things before time j
	int F(int i, int j) {
		int a = prev(upper_bound(AI(g[i]), make_pair(j+1, -1)))->second;
		return i == a ? i : F(a, j);
	}
	int F(int i) { return i == g[i].back().second ? i : F(g[i].back().second); }

	void M(int a, int b, int t) {
		bool ok = max(++deg[a], ++deg[b]) > 2;
		a = F(a), b = F(b);
		if (a == b) {
			chmin(ok_t[a], t);
			return good[a] = true, void();
		}
		if (sz[a] < sz[b]) swap(a, b);

		if (good[a] |= ok || good[b])
			chmin(ok_t[a], t);

		g[b].pb(t, a);
		sz[a] += sz[b];

	}
}D;

bool valid(int t, int a, int b) {
	a = D.F(a, t), b = D.F(b, t);
	if (a != b) return false;
	return ok_t[a] <= t;
}

int n, m;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

	n = N, m = M;
	D = dsu(n);

	vector<tuple<int,int,int>> alle;
	for (int i = 0;i < m;++i) {
		alle.pb(W[i], U[i], V[i]);
	}
	sort(AI(alle));

	for (int i = 0;i < n;++i)
		ok_t[i] = inf;

	for (int i = 0;i < m;++i) {
		auto [w, a, b] = alle[i];
		wei[i] = w;

		D.M(a, b, i);
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int l = 0, r = m-1, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (valid(mid, X, Y))
			r = mid;
		else
			l = mid + 1;
	}
	return valid(l, X, Y) ? wei[l] : -1;
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:90:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |   mid = l + r >> 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