Submission #394169

#	Time	Username	Problem	Language	Result	Execution time	Memory
394169		hoaphat1	Swapping Cities (APIO20_swap)	C++17	0 / 100	2074 ms	11996 KiB

swap

#include<bits/stdc++.h>

using namespace std;

struct dsu {
	vector<int> p;
	dsu(int n) {
		p.resize(n, -1);
	}
	int get(int x) {
		return p[x] < 0 ? x : p[x]  = get(p[x]);
	}
	bool unite(int x, int y) {
		x = get(x); 
		y = get(y);
		if (x != y) {
			if (p[x] < p[y]) swap(x, y);
			p[y] += p[x];
			p[x] = y;
			return true;
		}
		return false;
	}
};

const int N = 1e5 + 3;
vector<tuple<int,int,int>> edges;
int n, m;
vector<int> g[N];

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
	for (int i = 0; i < M; i++) {
		edges.emplace_back(w[i], u[i], v[i]);
	}
	n = N;
	m = M;
}

int getMinimumFuelCapacity(int x, int y) {
	auto test = [&](int val) {
		for (int i = 0; i < n; i++) g[i].clear();
		dsu ds(n);
		for (int i = 0; i < m; i++) {
			if (get<0>(edges[i]) <= val) {
				g[get<1>(edges[i])].push_back(get<2>(edges[i]));
				g[get<2>(edges[i])].push_back(get<1>(edges[i]));
				ds.unite(get<1>(edges[i]), get<2>(edges[i]));
			}
		}
		vector<vector<int>> d(2, vector<int> (n));
		auto dijkstra = [&](int s, vector<int>& d) {
			for (int i = 0; i < n; i++) d[i] = (int) 1e9;
			d[s] = 0;
			deque<int> q = {s};
			while (!q.empty()) {
				int v = q.front(); q.pop_front();
				for (auto&u : g[v]) {
					if (d[u] > d[v] + 1) {
						d[u] = d[v] + 1;
						q.push_back(u);
					}
				}
			}
		};
		dijkstra(x, d[0]);
		return (d[0][y] + 1 < -ds.p[ds.get(y)]);
		/*dijkstra(y, d[1]);
		vector<bool> precious(n);
		for (int i = 0; i < n; i++) precious[i] = !(d[0][i] + d[1][i] == d[0][y]);
		vector<int> can(2 * n);
		can[x] = 1;
		deque<int> q = {x};
		while (!q.empty()) {
			int v = q.front(); q.pop_front();
			if (v % n == y) continue;
			int type = v / n;
			bool flag = false;
			for (auto&u : g[v % n]) {
				flag |= precious[u];
				if (d[0][v % n] > d[0][u]) continue;
				if (!type && can[u] && !can[u + n]) {
					can[u + n] = 1;
					q.push_back(u + n);
				}
				if (!can[u + type * n]) {
					can[u + type * n] = 1;
					q.push_back(u + type * n); 
				}
			}
			if (flag && !type && !can[v + n]) {
				can[v + n] = 1;
				q.push_back(v + n);
			}
		}
		return can[n + y];*/
	};
	int l = 0, r = (int)1e9;
	while (l <= r) {
		int mid = l + r >> 1;
		if (test(mid)) r = mid - 1;
		else l = mid + 1;
	}
	if (l == (int) 1e9 + 1) l = -1;
	return l;
}
 /*
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N = 4, M = 3;
	vector<int> U = {0, 0, 0};
	vector<int> V = {1, 2, 3};
	vector<int> W = {1, 2, 3};
	init(N, M, U, V, W);
	int q = 1;
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << getMinimumFuelCapacity(x, y) << "\n" << flush;
	} 
}*/

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:99:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |   int mid = l + r >> 1;
      |             ~~^~~

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