Submission #394165

#	Time	Username	Problem	Language	Result	Execution time	Memory
394165		hoaphat1	Swapping Cities (APIO20_swap)	C++17	0 / 100	2079 ms	23372 KiB

swap

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 3;
vector<tuple<int,int,int>> edges;
int n, m;
set<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();
		for (int i = 0; i < m; i++) {
			if (get<0>(edges[i]) <= val) {
				g[get<1>(edges[i])].insert(get<2>(edges[i]));
				g[get<2>(edges[i])].insert(get<1>(edges[i]));
			}
		}
		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;
			for (auto&u : g[v % n]) {
				if (!type && can[u] && !can[u + n]) {
					can[u + n] = 1;
					q.push_back(u + n);
					g[u].erase(v);
				}
				if (!can[u + type * n]) {
					can[u + type * n] = 1;
					q.push_back(u + type * n); 
					g[u].erase(v);
				}
				
			}
		}
		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 = 5, M = 6;
	vector<int> U = {0, 0, 1, 1, 1, 2};
	vector<int> V = {1, 2, 2, 3, 4, 3};
	vector<int> W = {4, 4, 1, 2, 10, 3};
	init(N, M, U, V, W);
	int q = 3;
	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:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   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