oj.uz

Submission #935134

# Submission time Handle Problem Language Result Execution time Memory
935134 2024-02-28T17:36:35 Z MinaRagy06 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 26040 KB 
#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const int N = 200'005;
int n, m;
array<int, 3> e[N];
vector<int> adj[N];
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
	n = _n, m = _m;
	for (int i = 0; i < m; i++) {
		e[i] = {u[i], v[i], w[i]};
	}
	sort(e, e + m, [&] (array<int, 3> x, array<int, 3> y) {return x[2] < y[2];});
}
int dist[N], ok[N], t[N], low[N], cur, vis[N], bad;
int dfs(int i, int p, int x, int y) {
	vis[i] = 1;
	t[i] = low[i] = cur++;
	int cnt = 0;
	for (auto nxt : adj[i]) {
		if (nxt == p) continue;
		if (vis[nxt]) {
			low[i] = min(low[i], t[nxt]);
		} else {
			int val = dfs(nxt, i, x, y);
			low[i] = min(low[i], low[nxt]);
			if (low[nxt] > t[i] && val == 1) {
				bad = 1;
			}
			cnt += val;
		}
	}
	cnt += i == x || i == y;
	return cnt;
}
int getMinimumFuelCapacity(int x, int y) {
	int l = 0, r = m - 1;
	while (l <= r) {
		int md = ((l + r) >> 1);
		for (int i = 0; i < n; i++) {
			adj[i].clear();
			dist[i] = 1e9;
			ok[i] = 0;
			vis[i] = 0;
		}
		bad = 0;
		for (int i = 0; i <= md; i++) {
			adj[e[i][0]].push_back(e[i][1]);
			adj[e[i][1]].push_back(e[i][0]);
		}
		queue<array<int, 2>> q;
		q.push({x, 0});
		dist[x] = 0;
		while (q.size()) {
			int i = q.front()[0];
			int c = q.front()[1];
			q.pop();
			if (i != x) ok[i] |= adj[i].size() > 2;
			for (auto nxt : adj[i]) {
				if (c + 1 < dist[nxt]) {
					dist[nxt] = c + 1;
					ok[nxt] = ok[i];
					q.push({nxt, c + 1});
				}
			}
		}
		dfs(x, -1, x, y);
// 		if (e[md][2] == 1) {
// 			cout << low[2] << ' ' << t[1] << '\n';
// 		}
		if (ok[y] || (vis[y] && !bad)) {
			r = md - 1;
		} else {
			l = md + 1;
		}
	}
	if (l == m) {
		return -1;
	}
	return e[l][2];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8644 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 92 ms 23148 KB Output is correct
10 Correct 207 ms 24852 KB Output is correct
11 Correct 233 ms 25080 KB Output is correct
12 Correct 273 ms 25244 KB Output is correct
13 Correct 380 ms 26040 KB Output is correct
14 Execution timed out 2025 ms 23580 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8644 KB Output is correct
3 Execution timed out 2060 ms 22228 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8644 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 2 ms 9048 KB Output is correct
10 Correct 2 ms 8788 KB Output is correct
11 Correct 3 ms 8536 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8536 KB Output is correct
15 Incorrect 4 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 2 ms 8644 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 92 ms 23148 KB Output is correct
11 Correct 207 ms 24852 KB Output is correct
12 Correct 233 ms 25080 KB Output is correct
13 Correct 273 ms 25244 KB Output is correct
14 Correct 380 ms 26040 KB Output is correct
15 Correct 2 ms 8788 KB Output is correct
16 Correct 3 ms 8536 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 3 ms 8540 KB Output is correct
19 Correct 3 ms 8536 KB Output is correct
20 Incorrect 4 ms 8540 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 2 ms 8644 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 92 ms 23148 KB Output is correct
10 Correct 207 ms 24852 KB Output is correct
11 Correct 233 ms 25080 KB Output is correct
12 Correct 273 ms 25244 KB Output is correct
13 Correct 380 ms 26040 KB Output is correct
14 Execution timed out 2025 ms 23580 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 2 ms 8644 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 92 ms 23148 KB Output is correct
11 Correct 207 ms 24852 KB Output is correct
12 Correct 233 ms 25080 KB Output is correct
13 Correct 273 ms 25244 KB Output is correct
14 Correct 380 ms 26040 KB Output is correct
15 Execution timed out 2025 ms 23580 KB Time limit exceeded
16 Halted 0 ms 0 KB -