oj.uz

Submission #97335

# Submission time Handle Problem Language Result Execution time Memory
97335 2019-02-15T09:45:18 Z E869120 Highway Tolls (IOI18_highway) C++14
51 / 100
 589 ms 31616 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> G[1<<18]; int depth[1<<18], par[1<<18], BB[1<<18]; bool anti[1<<18];
map<pair<int, int>, int>M;

void dfs(int pos, int dep) {
	depth[pos] = dep;
	for (int i = 0; i < G[pos].size(); i++) {
		if(depth[G[pos][i]] != -1) continue;
		par[G[pos][i]] = pos;
		BB[G[pos][i]] = M[make_pair(G[pos][i], pos)];
		dfs(G[pos][i], dep + 1);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	for (int i = 0; i < U.size(); i++) {
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
		M[make_pair(U[i], V[i])] = i; M[make_pair(V[i], U[i])] = i;
	}
	for (int i = 0; i < N; i++) depth[i] = -1;
	dfs(0, 0);
	
	vector<int> W(N - 1, 0);
	for (int i = 0; i < N - 1; i++) W[i] = 0; long long c1 = ask(W);
	for (int i = 0; i < N - 1; i++) W[i] = 1; long long c2 = ask(W);
	
	vector<pair<int, int>> T;
	for (int i = 1; i < N; i++) T.push_back(make_pair(depth[i], i));
	sort(T.begin(), T.end());
	
	// Part 1. Find the lowest
	int L1 = 0, R1 = N - 1, M1, ret1 = 0;
	for (int i = 0; i < 19; i++) {
		M1 = (L1 + R1) / 2;
		for (int j = 0; j < T.size(); j++) { if (j < M1) W[BB[T[j].second]] = 0; else W[BB[T[j].second]] = 1; }
		long long c3 = ask(W);
		if (c1 == c3) { R1 = M1; }
		else { L1 = M1; ret1 = max(ret1, M1); }
	}
	
	int cx = T[ret1].second;
	while (true) {
		anti[cx] = true; if (cx == 0) break;
		cx = par[cx];
	}
	
	// Part 2. Find the highest
	int L2 = 0, R2 = N - 1, M2, ret2 = N - 2;
	for (int i = 0; i < 19; i++) {
		M2 = (L2 + R2) / 2;
		for (int j = 0; j < T.size(); j++) { if (j <= M2) W[BB[T[j].second]] = 1; else W[BB[T[j].second]] = 0; }
		long long c3 = ask(W);
		if (c1 == c3) { L2 = M2; }
		else { R2 = M2; ret2 = min(ret2, M2);  }
	}
	
	// Part 3. Find the second
	long long P1 = T[ret1].first, P2 = T[ret2].first - 1, Leng = (c2 - c1) / (1LL * B - 1LL * A);
	long long P3 = P2 + (Leng - (P1 - P2));
	
	if (P3 == P2) {
		answer(par[T[ret2].second], T[ret1].second);
		return;
	}
	
	vector<int>I;
	for (int i = 0; i < N; i++) {
		if (depth[i] == P3 && anti[i] == false) { I.push_back(i); }
	}
	
	int L3 = 0, R3 = I.size(), M3, ret3 = I.size() - 1;
	for (int i = 0; i < 19; i++) {
		M3 = (L3 + R3) / 2;
		for (int j = 0; j < N; j++) W[j] = 0;
		for (int j = 0; j <= M3; j++) W[BB[I[j]]] = 1;
		
		long long c3 = ask(W);
		if (c1 == c3) { L3 = M3; }
		else { R3 = M3; ret3 = min(ret3, M3); }
	}
	
	answer(I[ret3], T[ret1].second);
	return;
}

Compilation message

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
highway.cpp:28:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i = 0; i < N - 1; i++) W[i] = 0; long long c1 = ask(W);
  ^~~
highway.cpp:28:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i = 0; i < N - 1; i++) W[i] = 0; long long c1 = ask(W);
                                            ^~~~
highway.cpp:29:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i = 0; i < N - 1; i++) W[i] = 1; long long c2 = ask(W);
  ^~~
highway.cpp:29:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i = 0; i < N - 1; i++) W[i] = 1; long long c2 = ask(W);
                                            ^~~~
highway.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < T.size(); j++) { if (j < M1) W[BB[T[j].second]] = 0; else W[BB[T[j].second]] = 1; }
                   ~~^~~~~~~~~~
highway.cpp:55:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < T.size(); j++) { if (j <= M2) W[BB[T[j].second]] = 1; else W[BB[T[j].second]] = 0; }
                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6440 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 8 ms 6516 KB Output is correct
4 Correct 8 ms 6512 KB Output is correct
5 Correct 7 ms 6392 KB Output is correct
6 Correct 8 ms 6520 KB Output is correct
7 Correct 8 ms 6520 KB Output is correct
8 Correct 8 ms 6392 KB Output is correct
9 Correct 8 ms 6392 KB Output is correct
10 Correct 8 ms 6392 KB Output is correct
11 Correct 8 ms 6516 KB Output is correct
12 Correct 8 ms 6440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6648 KB Output is correct
2 Correct 42 ms 8600 KB Output is correct
3 Correct 490 ms 24660 KB Output is correct
4 Correct 488 ms 24668 KB Output is correct
5 Correct 510 ms 24660 KB Output is correct
6 Correct 491 ms 24664 KB Output is correct
7 Correct 456 ms 24640 KB Output is correct
8 Correct 504 ms 24640 KB Output is correct
9 Correct 469 ms 24580 KB Output is correct
10 Correct 442 ms 24668 KB Output is correct
11 Correct 524 ms 26272 KB Output is correct
12 Correct 528 ms 27012 KB Output is correct
13 Correct 544 ms 26356 KB Output is correct
14 Correct 517 ms 25736 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9388 KB Output is correct
2 Correct 48 ms 12124 KB Output is correct
3 Correct 92 ms 14884 KB Output is correct
4 Correct 270 ms 31612 KB Output is correct
5 Correct 273 ms 31604 KB Output is correct
6 Correct 262 ms 31616 KB Output is correct
7 Correct 282 ms 31516 KB Output is correct
8 Correct 264 ms 31592 KB Output is correct
9 Correct 274 ms 31616 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6684 KB Output is correct
2 Correct 44 ms 8624 KB Output is correct
3 Correct 383 ms 20808 KB Output is correct
4 Correct 502 ms 24796 KB Output is correct
5 Correct 463 ms 24760 KB Output is correct
6 Correct 524 ms 24712 KB Output is correct
7 Correct 484 ms 24632 KB Output is correct
8 Correct 499 ms 24572 KB Output is correct
9 Correct 589 ms 24676 KB Output is correct
10 Correct 507 ms 24664 KB Output is correct
11 Correct 528 ms 25616 KB Output is correct
12 Correct 536 ms 27128 KB Output is correct
13 Correct 538 ms 26448 KB Output is correct
14 Correct 548 ms 27060 KB Output is correct
15 Correct 512 ms 24652 KB Output is correct
16 Correct 449 ms 24628 KB Output is correct
17 Correct 531 ms 26760 KB Output is correct
18 Correct 553 ms 26220 KB Output is correct
19 Correct 513 ms 24608 KB Output is correct
20 Correct 509 ms 27592 KB Output is correct
21 Correct 493 ms 25376 KB Output is correct
22 Correct 432 ms 25372 KB Output is correct
23 Correct 441 ms 25096 KB Output is correct
24 Correct 463 ms 25748 KB Output is correct
25 Correct 577 ms 30484 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 8612 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 8736 KB Incorrect
2 Halted 0 ms 0 KB -