Submission #1008678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1008678	2024-06-26T16:35:40 Z	overwatch9	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	15260 KB

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;
	DSU (int s) {
		link = sz = vector <int> (s+1);
		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;
	}
};
int getMinimumFuelCapacity(int x, int y) {
	DSU dsu(n+1);
	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);
			if (dsu.same(x, y) && dsu.cycle[dsu.head(a)])
				return edges[i][2];
		}
		else {
			dsu.cycle[dsu.head(a)] = true;
			if (dsu.same(a, x)) {
				if (dsu.same(x, y)) {
					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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	464 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	37 ms	9728 KB	Output is correct
10	Correct	47 ms	11016 KB	Output is correct
11	Correct	50 ms	11016 KB	Output is correct
12	Correct	56 ms	11528 KB	Output is correct
13	Correct	48 ms	11528 KB	Output is correct
14	Execution timed out	2036 ms	10000 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Execution timed out	2045 ms	15260 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	464 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Incorrect	1 ms	348 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	436 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	464 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	37 ms	9728 KB	Output is correct
11	Correct	47 ms	11016 KB	Output is correct
12	Correct	50 ms	11016 KB	Output is correct
13	Correct	56 ms	11528 KB	Output is correct
14	Correct	48 ms	11528 KB	Output is correct
15	Incorrect	1 ms	348 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	0 ms	436 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	464 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	37 ms	9728 KB	Output is correct
10	Correct	47 ms	11016 KB	Output is correct
11	Correct	50 ms	11016 KB	Output is correct
12	Correct	56 ms	11528 KB	Output is correct
13	Correct	48 ms	11528 KB	Output is correct
14	Execution timed out	2036 ms	10000 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	0 ms	436 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	464 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	37 ms	9728 KB	Output is correct
11	Correct	47 ms	11016 KB	Output is correct
12	Correct	50 ms	11016 KB	Output is correct
13	Correct	56 ms	11528 KB	Output is correct
14	Correct	48 ms	11528 KB	Output is correct
15	Execution timed out	2036 ms	10000 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-