oj.uz

Submission #1008681

# Submission time Handle Problem Language Result Execution time Memory
1008681 2024-06-26T16:36:46 Z overwatch9 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 13472 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;
	}
};
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 460 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 54 ms 8956 KB Output is correct
10 Correct 50 ms 10252 KB Output is correct
11 Correct 53 ms 10256 KB Output is correct
12 Correct 57 ms 10696 KB Output is correct
13 Correct 54 ms 10504 KB Output is correct
14 Execution timed out 2070 ms 9376 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 2017 ms 13472 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 460 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 344 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 344 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 460 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 54 ms 8956 KB Output is correct
11 Correct 50 ms 10252 KB Output is correct
12 Correct 53 ms 10256 KB Output is correct
13 Correct 57 ms 10696 KB Output is correct
14 Correct 54 ms 10504 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 460 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 54 ms 8956 KB Output is correct
10 Correct 50 ms 10252 KB Output is correct
11 Correct 53 ms 10256 KB Output is correct
12 Correct 57 ms 10696 KB Output is correct
13 Correct 54 ms 10504 KB Output is correct
14 Execution timed out 2070 ms 9376 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 344 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 460 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 54 ms 8956 KB Output is correct
11 Correct 50 ms 10252 KB Output is correct
12 Correct 53 ms 10256 KB Output is correct
13 Correct 57 ms 10696 KB Output is correct
14 Correct 54 ms 10504 KB Output is correct
15 Execution timed out 2070 ms 9376 KB Time limit exceeded
16 Halted 0 ms 0 KB -