oj.uz

Submission #248588

# Submission time Handle Problem Language Result Execution time Memory
248588 2020-07-12T19:47:18 Z kostia244 Highway Tolls (IOI18_highway) C++17
90 / 100
 382 ms 19576 KB 
#include "highway.h"
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<17;
using ll = long long;
int n, m;
vector<int> c, res, d, edges;
vector<array<int, 2>> g[maxn], G[maxn], edgelist;
int D, a, b;
bool go(vector<int> c, int p) {
	vector<int> w(m, 0);
	for(int i = 0; i <= p; i++) w[c[i]] = 1;
	int res = ask(w) == a*1ll*D;
	//for(auto &i : w) cout << i;cout << " " << res << endl;
	return res;
}
int findroot() {
	int p = -1;
	vector<int> al;
	for(int i = 0; i < m; i++) al.push_back(i);
	for(int i = 1<<17; i>>=1;)
		if(p+i < m && go(al, p+i)) p += i;
	return edgelist[++p][0];
}
void reroot(int root) {
	//cout << "Root at " << root << " Faggot!\n";
	queue<int> q;
	d = vector<int>(n, 1<<30);
	for(int i = 1; i <= n; i++) g[i].clear();
	q.push({root});
	d[root] = 0;
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		for(auto [u, id] : G[v]) {
			ll nd = d[v] + 1;
			if(d[u] > nd) {
				g[u].push_back({v, id});
				g[v].push_back({u, id});
				d[u] = nd;
				q.push(u);
			}
		}
	}
	for(auto &[x, y] : edgelist) if(d[x] < d[y]) swap(x, y);
	sort(edges.begin(), edges.end(), [](auto _i, auto _j) {
		auto i = edgelist[_i], j = edgelist[_j];
		return array<int, 2>{d[i[0]], d[i[1]]} > array<int, 2>{d[j[0]], d[j[1]]};
	});
	//for(auto &i : edges) cout << edgelist[i][0] << " " << edgelist[i][1] << '\n';
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	a = A, b = B;
	m = U.size();
	for(int i = 0; i < m; i++) edges.push_back(i);
	int s3 = 1;
	for(int i = 0; i < U.size(); i++) {
		s3 &= U[i] == i && V[i] == i+1;
		edgelist.push_back({U[i], V[i]});
		G[U[i]].push_back({V[i], i});
		G[V[i]].push_back({U[i], i});
	}
	D = ask(vector<int>(m))/A;
	reroot(findroot());
	int p = -1;
	for(int i = 1<<17; i>>=1;)
		if(p+i < m && go(edges, p+i)) p += i;
	int s = edgelist[edges[++p]][0];
	
	reroot(s);
	p = -1;
	for(int i = 1<<17; i>>=1;)
		if(p+i < m && go(edges, p+i)) p += i;
	int t = edgelist[edges[++p]][0];
	//cout << s << " " << t << endl;
	answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB Output is correct
2 Correct 19 ms 7648 KB Output is correct
3 Correct 196 ms 17088 KB Output is correct
4 Correct 215 ms 17184 KB Output is correct
5 Correct 205 ms 17164 KB Output is correct
6 Correct 178 ms 16812 KB Output is correct
7 Correct 196 ms 16820 KB Output is correct
8 Correct 193 ms 16812 KB Output is correct
9 Correct 271 ms 16828 KB Output is correct
10 Correct 185 ms 16940 KB Output is correct
11 Correct 220 ms 16084 KB Output is correct
12 Correct 269 ms 15732 KB Output is correct
13 Correct 237 ms 15724 KB Output is correct
14 Correct 271 ms 15720 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7508 KB Output is correct
2 Correct 32 ms 8580 KB Output is correct
3 Correct 48 ms 9604 KB Output is correct
4 Correct 205 ms 15724 KB Output is correct
5 Correct 164 ms 15748 KB Output is correct
6 Correct 184 ms 15712 KB Output is correct
7 Correct 198 ms 15768 KB Output is correct
8 Correct 139 ms 15780 KB Output is correct
9 Correct 187 ms 15736 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6656 KB Output is correct
2 Correct 19 ms 7648 KB Output is correct
3 Correct 179 ms 14828 KB Output is correct
4 Correct 248 ms 16820 KB Output is correct
5 Correct 210 ms 16824 KB Output is correct
6 Correct 250 ms 16904 KB Output is correct
7 Correct 263 ms 16820 KB Output is correct
8 Correct 262 ms 16956 KB Output is correct
9 Correct 265 ms 17160 KB Output is correct
10 Correct 232 ms 16824 KB Output is correct
11 Correct 263 ms 15720 KB Output is correct
12 Correct 221 ms 16184 KB Output is correct
13 Correct 243 ms 16216 KB Output is correct
14 Correct 270 ms 15724 KB Output is correct
15 Correct 240 ms 16824 KB Output is correct
16 Correct 181 ms 16824 KB Output is correct
17 Correct 265 ms 15732 KB Output is correct
18 Correct 276 ms 15732 KB Output is correct
19 Correct 231 ms 16836 KB Output is correct
20 Correct 193 ms 16060 KB Output is correct
21 Correct 197 ms 17488 KB Output is correct
22 Correct 208 ms 17564 KB Output is correct
23 Correct 157 ms 17304 KB Output is correct
24 Correct 189 ms 17244 KB Output is correct
25 Correct 184 ms 15952 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7668 KB Output is correct
2 Correct 28 ms 7912 KB Output is correct
3 Correct 236 ms 17656 KB Output is correct
4 Correct 234 ms 18212 KB Output is correct
5 Correct 277 ms 19576 KB Output is correct
6 Correct 279 ms 19420 KB Output is correct
7 Correct 281 ms 19384 KB Output is correct
8 Correct 283 ms 19396 KB Output is correct
9 Correct 218 ms 15788 KB Output is correct
10 Correct 220 ms 16136 KB Output is correct
11 Correct 213 ms 17464 KB Output is correct
12 Correct 356 ms 18400 KB Output is correct
13 Correct 338 ms 19020 KB Output is correct
14 Correct 302 ms 19296 KB Output is correct
15 Correct 286 ms 19380 KB Output is correct
16 Correct 301 ms 16744 KB Output is correct
17 Correct 178 ms 17948 KB Output is correct
18 Correct 148 ms 18220 KB Output is correct
19 Correct 163 ms 18132 KB Output is correct
20 Correct 210 ms 18200 KB Output is correct
21 Correct 310 ms 19144 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 7668 KB Output is correct
2 Correct 26 ms 7784 KB Output is correct
3 Correct 291 ms 17700 KB Output is correct
4 Partially correct 291 ms 17912 KB Output is partially correct
5 Partially correct 309 ms 18252 KB Output is partially correct
6 Partially correct 278 ms 19412 KB Output is partially correct
7 Partially correct 213 ms 17692 KB Output is partially correct
8 Correct 271 ms 17896 KB Output is correct
9 Correct 279 ms 18176 KB Output is correct
10 Partially correct 296 ms 19484 KB Output is partially correct
11 Partially correct 295 ms 19536 KB Output is partially correct
12 Partially correct 328 ms 19412 KB Output is partially correct
13 Correct 297 ms 17456 KB Output is correct
14 Partially correct 215 ms 16080 KB Output is partially correct
15 Correct 202 ms 16736 KB Output is correct
16 Correct 237 ms 16124 KB Output is correct
17 Partially correct 198 ms 17536 KB Output is partially correct
18 Partially correct 192 ms 16128 KB Output is partially correct
19 Partially correct 268 ms 18508 KB Output is partially correct
20 Partially correct 273 ms 19124 KB Output is partially correct
21 Partially correct 285 ms 19432 KB Output is partially correct
22 Partially correct 369 ms 19340 KB Output is partially correct
23 Partially correct 378 ms 19280 KB Output is partially correct
24 Partially correct 298 ms 19328 KB Output is partially correct
25 Partially correct 282 ms 19400 KB Output is partially correct
26 Partially correct 299 ms 19268 KB Output is partially correct
27 Partially correct 157 ms 18084 KB Output is partially correct
28 Partially correct 148 ms 17992 KB Output is partially correct
29 Partially correct 150 ms 18332 KB Output is partially correct
30 Partially correct 153 ms 18160 KB Output is partially correct
31 Partially correct 147 ms 18140 KB Output is partially correct
32 Partially correct 149 ms 17960 KB Output is partially correct
33 Partially correct 155 ms 18340 KB Output is partially correct
34 Partially correct 223 ms 18128 KB Output is partially correct
35 Partially correct 207 ms 18044 KB Output is partially correct
36 Partially correct 209 ms 18080 KB Output is partially correct
37 Partially correct 214 ms 18296 KB Output is partially correct
38 Partially correct 217 ms 18168 KB Output is partially correct
39 Partially correct 382 ms 19160 KB Output is partially correct
40 Partially correct 375 ms 19124 KB Output is partially correct
41 Partially correct 281 ms 19240 KB Output is partially correct
42 Partially correct 378 ms 19360 KB Output is partially correct