oj.uz

Submission #75245

# Submission time Handle Problem Language Result Execution time Memory
75245 2018-09-08T22:11:50 Z Xellos Highway Tolls (IOI18_highway) C++14
100 / 100
 664 ms 20328 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#include "highway.h"
using namespace std;

using cat = long long;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  vector<int> vq(M, 1);
  cat L = ask(vq) / B;
  // find edge on shortest path
  int el = 0, er = M;
  while(er - el > 1) {
  	int em = (el + er + 1) / 2;
  	for(int i = 0; i < em; i++) vq[i] = 0;
  	for(int i = em; i < M; i++) vq[i] = 1;
  	cat ans = ask(vq);
  	if(ans == L * A) er = em;
  	else el = em;
  }
  vector< vector< pair<int, int> > > G(N);
  for(int i = 0; i <= el; i++) {
  	G[U[i]].push_back({V[i], i});
  	G[V[i]].push_back({U[i], i});
  }
  // BFS graph for 2
  queue<int> q;
  vector<int> dep2(N, -1), v2;
  vector< vector<int> > e2_in(N);
  q.push(U[el]);
  dep2[U[el]] = 0;
  while(!q.empty()) {
  	v2.push_back(q.front());
  	for(auto e: G[q.front()]) if(dep2[e.ff] == -1) {
  		dep2[e.ff] = dep2[q.front()]+1;
  		q.push(e.ff);
  	}
  	q.pop();
  }
  for(int i = 0; i <= el; i++) {
  	if(dep2[U[i]] > dep2[V[i]]) e2_in[U[i]].push_back(i);
  	if(dep2[U[i]] < dep2[V[i]]) e2_in[V[i]].push_back(i);
  }
  int v2l = 0, v2r = v2.size();
  while(dep2[v2[v2r-1]] > L) v2r--;
  while(v2r-v2l > 1) {
  	int v2m = (v2l + v2r + 1) / 2;
  	for(int i = 0; i < M; i++) vq[i] = 1;
  	for(int i = 0; i < v2m; i++)
  		for(auto e: e2_in[v2[i]]) vq[e] = 0;
  	cat ans = ask(vq);
  	if(ans == L * A) v2r = v2m;
  	else v2l = v2m;
  }
  int S = v2[v2l];
  vector<bool> bl(N, false);
  vector<int> e_bl;
  int cur = S;
  while(dep2[cur] > 0) {
	bl[cur] = true;
  	for(auto e: G[cur]) if(dep2[e.ff] == dep2[cur]-1) {
  		e_bl.push_back(e.ss);
  		cur = e.ff;
  		break;
  	}
  }
  // BFS graph for 1
  vector<int> dep1(N, -1), v1;
  vector< vector<int> > e1_in(N);
  q.push(U[el]);
  dep1[U[el]] = 0;
  while(!q.empty()) {
  	v1.push_back(q.front());
  	for(auto e: G[q.front()]) if(!bl[e.ff] && dep1[e.ff] == -1) {
  		dep1[e.ff] = dep1[q.front()]+1;
  		q.push(e.ff);
  	}
  	q.pop();
  }
  for(int i = 0; i <= el; i++) if(!bl[U[i]] && !bl[V[i]]) {
  	if(dep1[U[i]] > dep1[V[i]]) e1_in[U[i]].push_back(i);
  	if(dep1[U[i]] < dep1[V[i]]) e1_in[V[i]].push_back(i);
  }
  int v1l = 0, v1r = v1.size();
  while(dep1[v1[v1r-1]] > L-dep2[S]) v1r--;
  while(v1r-v1l > 1) {
  	int v1m = (v1l + v1r + 1) / 2;
  	for(int i = 0; i < M; i++) vq[i] = 1;
  	for(auto e: e_bl) vq[e] = 0;
  	for(int i = 0; i < v1m; i++)
  		for(auto e: e1_in[v1[i]]) vq[e] = 0;
  	cat ans = ask(vq);
  	if(ans == L * A) v1r = v1m;
  	else v1l = v1m;
  }
  int T = v1[v1l];
  answer(S, T);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 316 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 8 ms 248 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 22 ms 1696 KB Output is correct
3 Correct 336 ms 15160 KB Output is correct
4 Correct 377 ms 15124 KB Output is correct
5 Correct 275 ms 15012 KB Output is correct
6 Correct 333 ms 14252 KB Output is correct
7 Correct 241 ms 14724 KB Output is correct
8 Correct 215 ms 13360 KB Output is correct
9 Correct 247 ms 14960 KB Output is correct
10 Correct 353 ms 14940 KB Output is correct
11 Correct 204 ms 13248 KB Output is correct
12 Correct 260 ms 13748 KB Output is correct
13 Correct 279 ms 15308 KB Output is correct
14 Correct 284 ms 14876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1276 KB Output is correct
2 Correct 37 ms 2820 KB Output is correct
3 Correct 50 ms 4964 KB Output is correct
4 Correct 148 ms 12748 KB Output is correct
5 Correct 151 ms 11344 KB Output is correct
6 Correct 185 ms 14648 KB Output is correct
7 Correct 186 ms 14836 KB Output is correct
8 Correct 140 ms 13292 KB Output is correct
9 Correct 161 ms 13744 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 22 ms 1656 KB Output is correct
3 Correct 161 ms 11748 KB Output is correct
4 Correct 216 ms 14480 KB Output is correct
5 Correct 222 ms 18304 KB Output is correct
6 Correct 221 ms 14376 KB Output is correct
7 Correct 166 ms 11484 KB Output is correct
8 Correct 198 ms 14544 KB Output is correct
9 Correct 427 ms 16224 KB Output is correct
10 Correct 259 ms 13880 KB Output is correct
11 Correct 355 ms 15284 KB Output is correct
12 Correct 471 ms 15828 KB Output is correct
13 Correct 393 ms 14308 KB Output is correct
14 Correct 339 ms 15144 KB Output is correct
15 Correct 163 ms 13860 KB Output is correct
16 Correct 225 ms 16548 KB Output is correct
17 Correct 329 ms 15144 KB Output is correct
18 Correct 296 ms 15244 KB Output is correct
19 Correct 137 ms 11392 KB Output is correct
20 Correct 160 ms 12148 KB Output is correct
21 Correct 236 ms 13028 KB Output is correct
22 Correct 363 ms 17104 KB Output is correct
23 Correct 337 ms 17404 KB Output is correct
24 Correct 405 ms 17460 KB Output is correct
25 Correct 505 ms 15824 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2064 KB Output is correct
2 Correct 56 ms 2352 KB Output is correct
3 Correct 290 ms 19216 KB Output is correct
4 Correct 322 ms 16300 KB Output is correct
5 Correct 278 ms 16356 KB Output is correct
6 Correct 318 ms 19544 KB Output is correct
7 Correct 316 ms 20232 KB Output is correct
8 Correct 317 ms 18932 KB Output is correct
9 Correct 204 ms 5444 KB Output is correct
10 Correct 224 ms 8724 KB Output is correct
11 Correct 301 ms 11484 KB Output is correct
12 Correct 318 ms 17088 KB Output is correct
13 Correct 306 ms 17264 KB Output is correct
14 Correct 353 ms 20180 KB Output is correct
15 Correct 371 ms 20000 KB Output is correct
16 Correct 297 ms 11864 KB Output is correct
17 Correct 329 ms 15716 KB Output is correct
18 Correct 369 ms 15420 KB Output is correct
19 Correct 477 ms 18464 KB Output is correct
20 Correct 262 ms 15340 KB Output is correct
21 Correct 352 ms 20320 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2208 KB Output is correct
2 Correct 33 ms 2092 KB Output is correct
3 Correct 268 ms 18944 KB Output is correct
4 Correct 334 ms 18952 KB Output is correct
5 Correct 307 ms 19176 KB Output is correct
6 Correct 336 ms 19872 KB Output is correct
7 Correct 256 ms 18996 KB Output is correct
8 Correct 248 ms 18392 KB Output is correct
9 Correct 242 ms 16040 KB Output is correct
10 Correct 346 ms 20328 KB Output is correct
11 Correct 521 ms 20260 KB Output is correct
12 Correct 317 ms 18584 KB Output is correct
13 Correct 214 ms 6296 KB Output is correct
14 Correct 217 ms 4916 KB Output is correct
15 Correct 189 ms 7320 KB Output is correct
16 Correct 247 ms 9044 KB Output is correct
17 Correct 335 ms 11028 KB Output is correct
18 Correct 234 ms 6424 KB Output is correct
19 Correct 299 ms 15796 KB Output is correct
20 Correct 270 ms 18564 KB Output is correct
21 Correct 357 ms 20028 KB Output is correct
22 Correct 394 ms 19932 KB Output is correct
23 Correct 331 ms 19956 KB Output is correct
24 Correct 426 ms 20080 KB Output is correct
25 Correct 287 ms 19612 KB Output is correct
26 Correct 437 ms 19800 KB Output is correct
27 Correct 304 ms 13628 KB Output is correct
28 Correct 253 ms 15556 KB Output is correct
29 Correct 207 ms 13068 KB Output is correct
30 Correct 371 ms 14712 KB Output is correct
31 Correct 338 ms 15624 KB Output is correct
32 Correct 430 ms 15924 KB Output is correct
33 Correct 331 ms 14344 KB Output is correct
34 Correct 343 ms 14376 KB Output is correct
35 Correct 232 ms 16232 KB Output is correct
36 Correct 232 ms 13080 KB Output is correct
37 Correct 256 ms 14384 KB Output is correct
38 Correct 238 ms 12904 KB Output is correct
39 Correct 362 ms 19760 KB Output is correct
40 Correct 350 ms 19680 KB Output is correct
41 Correct 664 ms 20184 KB Output is correct
42 Correct 367 ms 20276 KB Output is correct