oj.uz

Submission #1010544

# Submission time Handle Problem Language Result Execution time Memory
1010544 2024-06-29T07:57:50 Z 정민찬(#10827) Highway Tolls (IOI18_highway) C++17
100 / 100
 150 ms 11788 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

long long ask(const std::vector<int> &w);
void answer(int s, int t);

vector<vector<pair<int,int>>> adj;

void getDist(int st, vector<int> &dist) {
	int N = adj.size();
	vector<int> vis(N, 0);
	queue<int> q;
	q.push(st);
	dist[st] = 0;
	vis[st] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto &[y, _] : adj[x]) {
			if (!vis[y]) {
				dist[y] = dist[x] + 1;
				vis[y] = 1;
				q.push(y);
			}
		}
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	adj.resize(N);
	int M = U.size();
	for (int i=0; i<M; i++) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}
	int cnt = 0;
	assert(cnt <= 51); cnt ++;
	ll mndist = ask(vector<int>(M, 0));
	int num = mndist / (ll)A;
	int s = 0, e = N-1;
	vector<int> t(M, 0);
	while (s < e) {
		int mid = s + e >> 1;
		vector<int> w = t;
		for (int i=s; i<=mid; i++) {
			for (auto &[j, k] : adj[i]) {
				w[k] = 1;
			}
		}
		assert(cnt <= 51); cnt ++;
		ll ret = ask(w);
		if (ret == mndist) s = mid + 1, t = w;
		else e = mid;
	}
	int rt = s;
	vector<int> dist(N);
	getDist(rt, dist);
	vector<int> idx(N);
	iota(idx.begin(), idx.end(), 0);
	sort(idx.begin(), idx.end(), [&] (int &x, int &y) { return dist[x] > dist[y]; });
	s = 0; e = N-1;
	for (int i=0; i<N; i++) {
		if (dist[idx[i]] * 2 < num) {
			e = i-1;
			break;
		}
	}
	if (num % 2 == 0) e --;
	while (s < e) {
		int mid = s + e >> 1;
		vector<int> w(M, 0);
		for (int i=0; i<=mid; i++) {
			for (auto &[j, k] : adj[idx[i]]) {
				w[k] = 1;
			}
		}
		assert(cnt <= 51); cnt ++;
		ll ret = ask(w);
		if (ret == mndist) s = mid + 1;
		else e = mid;
	}
	int u = idx[s];
	vector<int> dist2(N);
	getDist(u, dist2);
	vector<int> cand;
	vector<int> rev(N);
	for (int i=0; i<N; i++) {
		rev[idx[i]] = i;
	}
	for (int i=0; i<N; i++) {
		if (rev[i] > s && dist[i] + dist[u] == num && (ll)A * (ll)dist2[i] == mndist) {
			cand.push_back(i);
		}
	}
	s = 0; e = cand.size() - 1;
	while (s < e) {
		int mid = s + e >> 1;
		vector<int> w(M, 0);
		for (int i=s; i<=mid; i++) {
			for (auto &[j, k] : adj[cand[i]]) {
				w[k] = 1;
			}
		}
		assert(cnt <= 51); cnt ++;
		ll ret = ask(w);
		if (ret == mndist) s = mid + 1;
		else e = mid;
	}
	int v = cand[s];
	answer(u, v);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid = s + e >> 1;
      |             ~~^~~
highway.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int mid = s + e >> 1;
      |             ~~^~~
highway.cpp:100:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |   int mid = s + e >> 1;
      |             ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1400 KB Output is correct
3 Correct 95 ms 8960 KB Output is correct
4 Correct 83 ms 9088 KB Output is correct
5 Correct 87 ms 9024 KB Output is correct
6 Correct 76 ms 8944 KB Output is correct
7 Correct 102 ms 8912 KB Output is correct
8 Correct 92 ms 8968 KB Output is correct
9 Correct 91 ms 9056 KB Output is correct
10 Correct 94 ms 8924 KB Output is correct
11 Correct 85 ms 8372 KB Output is correct
12 Correct 88 ms 8476 KB Output is correct
13 Correct 86 ms 8308 KB Output is correct
14 Correct 77 ms 8356 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1112 KB Output is correct
2 Correct 15 ms 2120 KB Output is correct
3 Correct 22 ms 3024 KB Output is correct
4 Correct 85 ms 8408 KB Output is correct
5 Correct 68 ms 8496 KB Output is correct
6 Correct 65 ms 8528 KB Output is correct
7 Correct 59 ms 8368 KB Output is correct
8 Correct 60 ms 8320 KB Output is correct
9 Correct 64 ms 8372 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 1276 KB Output is correct
3 Correct 71 ms 7396 KB Output is correct
4 Correct 79 ms 9256 KB Output is correct
5 Correct 91 ms 9256 KB Output is correct
6 Correct 90 ms 9464 KB Output is correct
7 Correct 90 ms 8896 KB Output is correct
8 Correct 103 ms 9396 KB Output is correct
9 Correct 98 ms 9392 KB Output is correct
10 Correct 95 ms 9008 KB Output is correct
11 Correct 74 ms 8652 KB Output is correct
12 Correct 80 ms 8532 KB Output is correct
13 Correct 93 ms 8884 KB Output is correct
14 Correct 87 ms 8396 KB Output is correct
15 Correct 96 ms 9032 KB Output is correct
16 Correct 89 ms 8980 KB Output is correct
17 Correct 96 ms 9004 KB Output is correct
18 Correct 96 ms 8420 KB Output is correct
19 Correct 92 ms 8956 KB Output is correct
20 Correct 82 ms 8296 KB Output is correct
21 Correct 72 ms 9904 KB Output is correct
22 Correct 83 ms 9532 KB Output is correct
23 Correct 92 ms 10092 KB Output is correct
24 Correct 68 ms 9840 KB Output is correct
25 Correct 85 ms 9040 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1500 KB Output is correct
2 Correct 12 ms 1456 KB Output is correct
3 Correct 110 ms 9644 KB Output is correct
4 Correct 115 ms 10376 KB Output is correct
5 Correct 135 ms 11244 KB Output is correct
6 Correct 138 ms 11400 KB Output is correct
7 Correct 118 ms 11292 KB Output is correct
8 Correct 124 ms 11248 KB Output is correct
9 Correct 95 ms 7364 KB Output is correct
10 Correct 114 ms 7692 KB Output is correct
11 Correct 112 ms 8656 KB Output is correct
12 Correct 134 ms 10276 KB Output is correct
13 Correct 130 ms 10292 KB Output is correct
14 Correct 129 ms 11344 KB Output is correct
15 Correct 138 ms 11788 KB Output is correct
16 Correct 112 ms 8676 KB Output is correct
17 Correct 83 ms 9736 KB Output is correct
18 Correct 87 ms 9816 KB Output is correct
19 Correct 82 ms 9744 KB Output is correct
20 Correct 86 ms 9904 KB Output is correct
21 Correct 150 ms 11260 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1368 KB Output is correct
2 Correct 11 ms 1460 KB Output is correct
3 Correct 106 ms 10264 KB Output is correct
4 Correct 110 ms 9908 KB Output is correct
5 Correct 101 ms 10280 KB Output is correct
6 Correct 135 ms 11420 KB Output is correct
7 Correct 104 ms 9932 KB Output is correct
8 Correct 105 ms 9672 KB Output is correct
9 Correct 127 ms 9748 KB Output is correct
10 Correct 145 ms 11200 KB Output is correct
11 Correct 140 ms 10736 KB Output is correct
12 Correct 138 ms 11420 KB Output is correct
13 Correct 105 ms 8260 KB Output is correct
14 Correct 97 ms 7728 KB Output is correct
15 Correct 104 ms 8256 KB Output is correct
16 Correct 105 ms 7716 KB Output is correct
17 Correct 103 ms 8252 KB Output is correct
18 Correct 101 ms 7756 KB Output is correct
19 Correct 130 ms 10416 KB Output is correct
20 Correct 136 ms 10916 KB Output is correct
21 Correct 139 ms 11276 KB Output is correct
22 Correct 129 ms 10892 KB Output is correct
23 Correct 126 ms 11504 KB Output is correct
24 Correct 130 ms 11424 KB Output is correct
25 Correct 143 ms 11352 KB Output is correct
26 Correct 131 ms 11228 KB Output is correct
27 Correct 88 ms 9776 KB Output is correct
28 Correct 72 ms 9688 KB Output is correct
29 Correct 82 ms 9980 KB Output is correct
30 Correct 89 ms 9876 KB Output is correct
31 Correct 94 ms 9688 KB Output is correct
32 Correct 72 ms 9724 KB Output is correct
33 Correct 86 ms 9900 KB Output is correct
34 Correct 69 ms 9644 KB Output is correct
35 Correct 82 ms 9704 KB Output is correct
36 Correct 72 ms 9700 KB Output is correct
37 Correct 80 ms 9828 KB Output is correct
38 Correct 82 ms 9804 KB Output is correct
39 Correct 129 ms 11404 KB Output is correct
40 Correct 110 ms 11188 KB Output is correct
41 Correct 106 ms 11392 KB Output is correct
42 Correct 124 ms 11384 KB Output is correct