oj.uz

Submission #769113

# Submission time Handle Problem Language Result Execution time Memory
769113 2023-06-29T07:51:58 Z ono_de206 Highway Tolls (IOI18_highway) C++14
100 / 100
 226 ms 15016 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 1e5 + 10;
vector<int> g[mxn], V[mxn];

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
	int m = u.size();
	for(int i = 0; i < m; i++) {
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
		V[v[i]].pb(i);
		V[u[i]].pb(i);
	}
	long long tot = ask(vector<int>(m));
	int l = 0, r = m - 1;
	while(l < r) {
		int mid = (r + l) / 2;
		vector<int> q(m);
		for(int i = 0; i <= mid; i++) {
			q[i] = 1;
		}
		if(ask(q) == tot) l = mid + 1;
		else r = mid;
	}
	int x = u[l], y = v[l], ans1, ans2;

	auto bfs = [&](int st) -> vector<int> {
		vector<int> ret(n, -1);
		ret[st] = 0;
		queue<int> q;
		q.push(st);
		while(q.size()) {
			int x = q.front();
			q.pop();
			for(int y : g[x]) {
				if(ret[y] != -1) continue;
				ret[y] = ret[x] + 1;
				q.push(y);
			}
		}
		return ret;
	};

	auto disX = bfs(x);
	auto disY = bfs(y);

	vector<int> vec;
	for(int i = 0; i < n; i++) {
		if(disX[i] < disY[i]) vec.pb(i);
	}
	sort(all(vec), [&](int it1, int it2) {
		return disX[it1] < disX[it2];
	});

	l = 0, r = vec.size();

	while(r - l > 1) {
		int mid = (l + r) / 2;
		vector<int> q(m);
		for(int i = mid; i < vec.size(); i++) {
			for(int id : V[vec[i]]) {
				q[id] = 1;
			}
		}
		if(ask(q) == tot) r = mid;
		else l = mid;
	}

	ans1 = vec[l];

	vec.clear();

	for(int i = 0; i < n; i++) {
		if(disY[i] < disX[i]) vec.pb(i);
	}
	sort(all(vec), [&](int it1, int it2) {
		return disY[it1] < disY[it2];
	});

	l = 0, r = vec.size();

	while(r - l > 1) {
		int mid = (l + r) / 2;
		vector<int> q(m);
		for(int i = mid; i < vec.size(); i++) {
			for(int id : V[vec[i]]) {
				q[id] = 1;
			}
		}
		if(ask(q) == tot) r = mid;
		else l = mid;
	}

	ans2 = vec[l];

	answer(ans1, ans2);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i = mid; i < vec.size(); i++) {
      |                    ~~^~~~~~~~~~~~
highway.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int i = mid; i < vec.size(); i++) {
      |                    ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 11 ms 5968 KB Output is correct
3 Correct 132 ms 13892 KB Output is correct
4 Correct 126 ms 13836 KB Output is correct
5 Correct 102 ms 13844 KB Output is correct
6 Correct 133 ms 13844 KB Output is correct
7 Correct 100 ms 13836 KB Output is correct
8 Correct 122 ms 13836 KB Output is correct
9 Correct 132 ms 13828 KB Output is correct
10 Correct 114 ms 13884 KB Output is correct
11 Correct 128 ms 13568 KB Output is correct
12 Correct 138 ms 13756 KB Output is correct
13 Correct 114 ms 13596 KB Output is correct
14 Correct 156 ms 13760 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5840 KB Output is correct
2 Correct 20 ms 6888 KB Output is correct
3 Correct 29 ms 7788 KB Output is correct
4 Correct 90 ms 13572 KB Output is correct
5 Correct 95 ms 13580 KB Output is correct
6 Correct 90 ms 13552 KB Output is correct
7 Correct 103 ms 13600 KB Output is correct
8 Correct 72 ms 13620 KB Output is correct
9 Correct 69 ms 13520 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 12 ms 5980 KB Output is correct
3 Correct 76 ms 11908 KB Output is correct
4 Correct 135 ms 13836 KB Output is correct
5 Correct 125 ms 13844 KB Output is correct
6 Correct 123 ms 13840 KB Output is correct
7 Correct 104 ms 13840 KB Output is correct
8 Correct 121 ms 13824 KB Output is correct
9 Correct 118 ms 13824 KB Output is correct
10 Correct 114 ms 13840 KB Output is correct
11 Correct 150 ms 13616 KB Output is correct
12 Correct 106 ms 13560 KB Output is correct
13 Correct 114 ms 13544 KB Output is correct
14 Correct 144 ms 13596 KB Output is correct
15 Correct 104 ms 13832 KB Output is correct
16 Correct 132 ms 13844 KB Output is correct
17 Correct 114 ms 13596 KB Output is correct
18 Correct 131 ms 13592 KB Output is correct
19 Correct 114 ms 13836 KB Output is correct
20 Correct 127 ms 13584 KB Output is correct
21 Correct 99 ms 14336 KB Output is correct
22 Correct 129 ms 14340 KB Output is correct
23 Correct 94 ms 14392 KB Output is correct
24 Correct 133 ms 14228 KB Output is correct
25 Correct 133 ms 13676 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 5968 KB Output is correct
2 Correct 13 ms 6020 KB Output is correct
3 Correct 116 ms 14048 KB Output is correct
4 Correct 155 ms 14380 KB Output is correct
5 Correct 180 ms 14944 KB Output is correct
6 Correct 151 ms 14988 KB Output is correct
7 Correct 219 ms 15012 KB Output is correct
8 Correct 208 ms 15008 KB Output is correct
9 Correct 93 ms 11208 KB Output is correct
10 Correct 136 ms 12068 KB Output is correct
11 Correct 144 ms 12108 KB Output is correct
12 Correct 152 ms 13988 KB Output is correct
13 Correct 145 ms 14532 KB Output is correct
14 Correct 219 ms 14812 KB Output is correct
15 Correct 164 ms 14832 KB Output is correct
16 Correct 127 ms 12648 KB Output is correct
17 Correct 112 ms 14444 KB Output is correct
18 Correct 135 ms 14632 KB Output is correct
19 Correct 119 ms 14484 KB Output is correct
20 Correct 131 ms 14664 KB Output is correct
21 Correct 226 ms 14860 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6012 KB Output is correct
2 Correct 17 ms 5968 KB Output is correct
3 Correct 138 ms 14128 KB Output is correct
4 Correct 145 ms 14240 KB Output is correct
5 Correct 187 ms 14496 KB Output is correct
6 Correct 199 ms 14912 KB Output is correct
7 Correct 144 ms 14176 KB Output is correct
8 Correct 148 ms 14140 KB Output is correct
9 Correct 159 ms 14280 KB Output is correct
10 Correct 189 ms 15016 KB Output is correct
11 Correct 211 ms 14892 KB Output is correct
12 Correct 179 ms 14976 KB Output is correct
13 Correct 161 ms 12256 KB Output is correct
14 Correct 95 ms 12056 KB Output is correct
15 Correct 97 ms 12188 KB Output is correct
16 Correct 130 ms 12036 KB Output is correct
17 Correct 159 ms 12232 KB Output is correct
18 Correct 128 ms 12044 KB Output is correct
19 Correct 192 ms 13868 KB Output is correct
20 Correct 192 ms 14324 KB Output is correct
21 Correct 220 ms 14712 KB Output is correct
22 Correct 158 ms 14672 KB Output is correct
23 Correct 215 ms 14616 KB Output is correct
24 Correct 188 ms 14736 KB Output is correct
25 Correct 175 ms 14756 KB Output is correct
26 Correct 162 ms 14704 KB Output is correct
27 Correct 113 ms 14588 KB Output is correct
28 Correct 122 ms 14412 KB Output is correct
29 Correct 87 ms 14772 KB Output is correct
30 Correct 112 ms 14608 KB Output is correct
31 Correct 115 ms 14548 KB Output is correct
32 Correct 167 ms 14400 KB Output is correct
33 Correct 165 ms 14764 KB Output is correct
34 Correct 109 ms 14536 KB Output is correct
35 Correct 86 ms 14520 KB Output is correct
36 Correct 107 ms 14372 KB Output is correct
37 Correct 146 ms 14740 KB Output is correct
38 Correct 141 ms 14552 KB Output is correct
39 Correct 170 ms 14860 KB Output is correct
40 Correct 155 ms 14628 KB Output is correct
41 Correct 180 ms 14688 KB Output is correct
42 Correct 159 ms 14896 KB Output is correct