oj.uz

Submission #1008714

# Submission time Handle Problem Language Result Execution time Memory
1008714 2024-06-26T16:56:02 Z overwatch9 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 14880 KB 
#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;
		if (cycle[b])
			cycle[a] = true;
		// cycle[a] |= cycle[b];
	}
};
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);
		}
		else {
			dsu.cycle[dsu.head(a)] = true;
			if (dsu.same(a, x)) {
				if (dsu.same(x, y)) {
					return edges[i][2];
				}
			}
		}
		if (dsu.same(x, y) && dsu.cycle[dsu.head(a)])
			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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 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 31 ms 9724 KB Output is correct
10 Correct 48 ms 11020 KB Output is correct
11 Correct 47 ms 10900 KB Output is correct
12 Correct 51 ms 11528 KB Output is correct
13 Correct 48 ms 11536 KB Output is correct
14 Execution timed out 2060 ms 9996 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 2064 ms 14880 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 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 31 ms 9724 KB Output is correct
11 Correct 48 ms 11020 KB Output is correct
12 Correct 47 ms 10900 KB Output is correct
13 Correct 51 ms 11528 KB Output is correct
14 Correct 48 ms 11536 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 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 31 ms 9724 KB Output is correct
10 Correct 48 ms 11020 KB Output is correct
11 Correct 47 ms 10900 KB Output is correct
12 Correct 51 ms 11528 KB Output is correct
13 Correct 48 ms 11536 KB Output is correct
14 Execution timed out 2060 ms 9996 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 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 31 ms 9724 KB Output is correct
11 Correct 48 ms 11020 KB Output is correct
12 Correct 47 ms 10900 KB Output is correct
13 Correct 51 ms 11528 KB Output is correct
14 Correct 48 ms 11536 KB Output is correct
15 Execution timed out 2060 ms 9996 KB Time limit exceeded
16 Halted 0 ms 0 KB -