Submission #1008752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008752		overwatch9	Swapping Cities (APIO20_swap)	C++17	37 / 100	2080 ms	19964 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

vector <vector <pair <int, int>>> adj;
vector <array <int, 3>> edges;
int n, m;
bool comp(array <int, 3> a, array <int, 3> b) {
	return a[2] < b[2];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);
    adj.resize(N+1);
	n = N;
	m = M;
    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]});
		edges.push_back({U[i], V[i], W[i]});
	}
	sort(edges.begin(), edges.end(), comp);
}
struct DSU {
	vector <int> link, sz;
	vector <bool> cycle, connected;
	DSU (int s) {
		link = sz = vector <int> (s+1);
		connected = cycle = vector <bool> (s+1);
		for (int i = 1; i <= s; i++) {
			link[i] = i;
			sz[i] = 1;
		}
	}
	int head(int x) {
		if (link[x] != x)
			return link[x] = head(link[x]);
		return x;
	}
	bool same(int a, int b) {
		return head(a) == head(b);
	}
	void unite(int a, int b) {
		a = head(a);
		b = head(b);
		if (sz[a] < sz[b])
			swap(a, b);
		sz[a] += sz[b];
		link[b] = a;
		if (cycle[b])
			cycle[a] = true;
		if (connected[b])
			connected[a] = true;
		// cycle[a] |= cycle[b];
	}
};
int getMinimumFuelCapacity(int x, int y) {
	DSU dsu(n+1);
	vector <int> connected(n);
	for (int i = 0; i < m; i++) {
		int a = edges[i][0], b = edges[i][1];
		if (!dsu.same(a, b)) {
			dsu.unite(a, b);
			connected[a]++;
			connected[b]++;
		}
		else {
			dsu.cycle[dsu.head(a)] = true;
			connected[a]++;
			connected[b]++;
			if (dsu.same(a, x)) {
				if (dsu.same(x, y)) {
					return edges[i][2];
				}
			}
		}
		if (connected[a] >= 3)
			dsu.connected[dsu.head(a)] = true;
		if (connected[b] >= 3)
			dsu.connected[dsu.head(b)] = true;
		if (dsu.same(x, y) && dsu.cycle[dsu.head(a)] && dsu.same(x, a))
			return edges[i][2];
		if (dsu.same(x, y)) {
			if (dsu.same(x, a) && dsu.connected[dsu.head(x)])
				return edges[i][2];
		}
	}
	return -1;
}
// int main() {
// 	int N, M;
// 	cin >> N >> M;
// 	vector <int> u(M), v(M), w(M);
// 	for (int i = 0; i < M; i++)
// 		cin >> u[i] >> v[i] >> w[i];
// 	init(N, M, u, v, w);
// 	int q;
// 	cin >> q;
// 	while (q--) {
// 		int x, y;
// 		cin >> x >> y;
// 		cout << getMinimumFuelCapacity(x, y) << '\n';
// 	}
// }

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