Submission #927292

#	Time	Username	Problem	Language	Result	Execution time	Memory
927292		TAhmed33	Swapping Cities (APIO20_swap)	C++17	37 / 100	2013 ms	23744 KiB

swap

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
vector <int> adj2[MAXN];
bool vis[MAXN];
int deg[MAXN];
vector <int> t;
int n;
void init (int N, int m, vector <int> u, vector <int> v, vector <int> w) {
	t = w; sort(t.begin(), t.end());
	n = N;
	for (int i = 0; i < m; i++) {
		adj[u[i]].push_back({v[i], w[i]});
		adj[v[i]].push_back({u[i], w[i]});
	}
}
bool flag;
int cnt2 = 0;
void dfs (int pos) {
	vis[pos] = 1;
	flag |= deg[pos] > 2;
	//cout << pos << " " << deg[pos] << '\n';
	cnt2 += deg[pos] == 1;
	for (auto j : adj2[pos]) {
		if (!vis[j]) {
			dfs(j);
		}
	}
}
int getMinimumFuelCapacity (int x, int y) {
	int l = 0, r = (int)t.size() - 1, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		for (int i = 0; i < n; i++) {
			adj2[i].clear(); vis[i] = 0; deg[i] = 0;
			for (auto [h, z] : adj[i]) {
				if (z <= t[mid]) {
					adj2[i].push_back(h);
					deg[i]++;
				}
			}
			//cout << (int)adj[i].size() << " " << deg[i] << ": " << (int)adj2[i].size() << '\n';
		}
		flag = 0; cnt2 = 0;
		dfs(x);
		//cout << flag << " " << cnt2 << '\n';
		if (!vis[y] || (!flag && cnt2 == 2)) {
			l = mid + 1;
		} else {
			r = mid - 1; ans = mid;
		}
	}
	return ans == -1 ? -1 : t[ans];
}

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