oj.uz

Submission #394165

# Submission time Handle Problem Language Result Execution time Memory
394165 2021-04-26T02:38:58 Z hoaphat1 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 23372 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 3;
vector<tuple<int,int,int>> edges;
int n, m;
set<int> g[N];

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
	for (int i = 0; i < M; i++) {
		edges.emplace_back(w[i], u[i], v[i]);
	}
	n = N;
	m = M;
}

int getMinimumFuelCapacity(int x, int y) {
	auto test = [&](int val) {
		for (int i = 0; i < n; i++) g[i].clear();
		for (int i = 0; i < m; i++) {
			if (get<0>(edges[i]) <= val) {
				g[get<1>(edges[i])].insert(get<2>(edges[i]));
				g[get<2>(edges[i])].insert(get<1>(edges[i]));
			}
		}
		vector<int> can(2 * n);
		can[x] = 1;
		deque<int> q = {x};
		while (!q.empty()) {
			int v = q.front(); q.pop_front();
			if (v % n == y) continue;
			int type = v / n;
			for (auto&u : g[v % n]) {
				if (!type && can[u] && !can[u + n]) {
					can[u + n] = 1;
					q.push_back(u + n);
					g[u].erase(v);
				}
				if (!can[u + type * n]) {
					can[u + type * n] = 1;
					q.push_back(u + type * n); 
					g[u].erase(v);
				}
				
			}
		}
		return can[n + y];
	};
	int l = 0, r = (int)1e9;
	while (l <= r) {
		int mid = l + r >> 1;
		if (test(mid)) r = mid - 1;
		else l = mid + 1;
	}
	if (l == (int) 1e9 + 1) l = -1;
	return l;
}
 /*
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N = 5, M = 6;
	vector<int> U = {0, 0, 1, 1, 1, 2};
	vector<int> V = {1, 2, 2, 3, 4, 3};
	vector<int> W = {4, 4, 1, 2, 10, 3};
	init(N, M, U, V, W);
	int q = 3;
	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << getMinimumFuelCapacity(x, y) << "\n" << flush;
	} 
}*/

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 12 ms 5008 KB Output is correct
5 Correct 22 ms 5132 KB Output is correct
6 Correct 24 ms 5016 KB Output is correct
7 Correct 27 ms 5148 KB Output is correct
8 Correct 28 ms 5136 KB Output is correct
9 Execution timed out 2075 ms 16868 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Execution timed out 2079 ms 23372 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 12 ms 5008 KB Output is correct
5 Correct 22 ms 5132 KB Output is correct
6 Correct 24 ms 5016 KB Output is correct
7 Correct 27 ms 5148 KB Output is correct
8 Correct 28 ms 5136 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Incorrect 28 ms 5116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 12 ms 5008 KB Output is correct
6 Correct 22 ms 5132 KB Output is correct
7 Correct 24 ms 5016 KB Output is correct
8 Correct 27 ms 5148 KB Output is correct
9 Correct 28 ms 5136 KB Output is correct
10 Execution timed out 2075 ms 16868 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4996 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 12 ms 5008 KB Output is correct
5 Correct 22 ms 5132 KB Output is correct
6 Correct 24 ms 5016 KB Output is correct
7 Correct 27 ms 5148 KB Output is correct
8 Correct 28 ms 5136 KB Output is correct
9 Execution timed out 2075 ms 16868 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Correct 3 ms 4996 KB Output is correct
5 Correct 12 ms 5008 KB Output is correct
6 Correct 22 ms 5132 KB Output is correct
7 Correct 24 ms 5016 KB Output is correct
8 Correct 27 ms 5148 KB Output is correct
9 Correct 28 ms 5136 KB Output is correct
10 Execution timed out 2075 ms 16868 KB Time limit exceeded
11 Halted 0 ms 0 KB -