Submission #935137

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
935137	2024-02-28T17:43:05 Z	MinaRagy06	Swapping Cities (APIO20_swap)	C++17	17 / 100	425 ms	10368 KB

swap

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const int N = 2005;
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][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();
			for (int j = 0; j < n; j++) {
				dist[i][j] = 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, y});
		dist[x][y] = 0;
		while (q.size()) {
			int i = q.front()[0];
			int j = q.front()[1];
			q.pop();
			for (auto nxt : adj[i]) {
				if (nxt != j && dist[nxt][j] != 0) {
					dist[nxt][j] = 0;
					q.push({nxt, j});
				}
			}
			for (auto nxt : adj[j]) {
				if (nxt != i && dist[i][nxt] != 0) {
					dist[i][nxt] = 0;
					q.push({i, nxt});
				}
			}
		}
		if (dist[y][x] == 0) {
			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	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	18 ms	4740 KB	Output is correct
5	Correct	79 ms	8796 KB	Output is correct
6	Correct	73 ms	8796 KB	Output is correct
7	Correct	112 ms	8792 KB	Output is correct
8	Correct	224 ms	8892 KB	Output is correct
9	Runtime error	20 ms	4444 KB	Execution killed with signal 11
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Runtime error	51 ms	8224 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	18 ms	4740 KB	Output is correct
5	Correct	79 ms	8796 KB	Output is correct
6	Correct	73 ms	8796 KB	Output is correct
7	Correct	112 ms	8792 KB	Output is correct
8	Correct	224 ms	8892 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	166 ms	9084 KB	Output is correct
11	Correct	160 ms	8796 KB	Output is correct
12	Correct	127 ms	9044 KB	Output is correct
13	Correct	114 ms	8792 KB	Output is correct
14	Correct	193 ms	9044 KB	Output is correct
15	Correct	92 ms	8796 KB	Output is correct
16	Correct	160 ms	9056 KB	Output is correct
17	Correct	147 ms	8796 KB	Output is correct
18	Correct	246 ms	9036 KB	Output is correct
19	Correct	182 ms	7200 KB	Output is correct
20	Correct	192 ms	8796 KB	Output is correct
21	Correct	208 ms	9560 KB	Output is correct
22	Correct	34 ms	2912 KB	Output is correct
23	Correct	161 ms	7000 KB	Output is correct
24	Correct	374 ms	10084 KB	Output is correct
25	Correct	232 ms	10332 KB	Output is correct
26	Correct	159 ms	8792 KB	Output is correct
27	Correct	102 ms	8904 KB	Output is correct
28	Correct	425 ms	10368 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	18 ms	4740 KB	Output is correct
6	Correct	79 ms	8796 KB	Output is correct
7	Correct	73 ms	8796 KB	Output is correct
8	Correct	112 ms	8792 KB	Output is correct
9	Correct	224 ms	8892 KB	Output is correct
10	Runtime error	20 ms	4444 KB	Execution killed with signal 11
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	18 ms	4740 KB	Output is correct
5	Correct	79 ms	8796 KB	Output is correct
6	Correct	73 ms	8796 KB	Output is correct
7	Correct	112 ms	8792 KB	Output is correct
8	Correct	224 ms	8892 KB	Output is correct
9	Runtime error	20 ms	4444 KB	Execution killed with signal 11
10	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	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	18 ms	4740 KB	Output is correct
6	Correct	79 ms	8796 KB	Output is correct
7	Correct	73 ms	8796 KB	Output is correct
8	Correct	112 ms	8792 KB	Output is correct
9	Correct	224 ms	8892 KB	Output is correct
10	Runtime error	20 ms	4444 KB	Execution killed with signal 11
11	Halted	0 ms	0 KB	-