oj.uz

Submission #97356

# Submission time Handle Problem Language Result Execution time Memory
97356 2019-02-15T12:53:02 Z E869120 Highway Tolls (IOI18_highway) C++14
90 / 100
 591 ms 37792 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

int N, M, U[1 << 18], V[1 << 18], dist[1 << 18], par[1 << 18], paredge[1 << 18];
vector<pair<int, int>> G[1 << 18]; bool anti[1 << 18];

vector<int> GG[1<<18]; int depth[1<<18], BB[1<<18];
map<pair<int, int>, int>MM;

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

void find_pair(int NN, vector<int> UU, vector<int> VV, int A, int B) {
	if (NN - 1 == (int)UU.size()) {
		N = NN;
		for (int i = 0; i < UU.size(); i++) {
			GG[UU[i]].push_back(VV[i]);
			GG[VV[i]].push_back(UU[i]);
			MM[make_pair(UU[i], VV[i])] = i; MM[make_pair(VV[i], UU[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;
	}
	// ----------------------------- Step 0: Input ---------------------------
	N = NN; M = UU.size();
	for (int i = 0; i < M; i++) { U[i] = UU[i]; V[i] = VV[i]; }
	
	// -------------------------- Step 1: Get All-A --------------------------
	vector<int> W(M, 0);
	long long BASE = ask(W), DIST = BASE / A;
	
	// ---------------------- Step 2: The Minimum Vertex ---------------------
	int c1 = 0;
	for (int i = 16; i >= 0; i--) {
		for (int j = 0; j < M; j++) {
			if (min(U[j], V[j]) >= c1 + (1 << i)) W[j] = 0;
			else W[j] = 1;
		}
		long long p1 = ask(W);
		if (p1 == BASE) { c1 += (1 << i); }
	}
	
	// -------------------------- Step 3: Make Tree --------------------------
	for (int i = 0; i < M; i++) {
		if (min(U[i], V[i]) < c1) continue;
		G[U[i]].push_back(make_pair(V[i], i));
		G[V[i]].push_back(make_pair(U[i], i));
	}
	
	for (int i = 0; i < N; i++) dist[i] = (1 << 30);
	
	queue<int> que; que.push(c1); dist[c1] = 0;
	while (!que.empty()) {
		int pos1 = que.front(); que.pop();
		
		for (int i = 0; i < G[pos1].size(); i++) {
			int to = G[pos1][i].first;
			if (dist[to] > dist[pos1] + 1) {
				dist[to] = dist[pos1] + 1;
				que.push(to);
			}
		}
	}
	
	for (int i = c1 + 1; i < N; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			int to = G[i][j].first;
			if (dist[i] > dist[to]) { par[i] = to; paredge[i] = G[i][j].second; break; }
		}
	}
	
	// ---------------------------- 4. Find T --------------------------------
	vector<pair<int, int>> V;
	for (int i = c1 + 1; i < N; i++) {
		if (dist[i] == (1 << 30)) continue;
		V.push_back(make_pair(dist[i], i));
	}
	sort(V.begin(), V.end());
	
	//for (int i = 0; i < V.size(); i++) cout << "V[" << i << "] = " << V[i].second << endl;
	
	int c2 = 0;
	for (int i = 16; i >= 0; i--) {
		for (int j = 0; j < W.size(); j++) W[j] = 1;
		for (int j = 0; j < c2 + (1 << i); j++) {
			if (j >= V.size()) break;
			W[paredge[V[j].second]] = 0;
		}
		long long p2 = ask(W);
		if (p2 != BASE) c2 += (1 << i);
	}
	
	// --------------------- 5. Find the candidate of S ----------------------
	long long T = V[c2].second, cand_dst = DIST - dist[T];
	if (cand_dst == 0) {
		answer(T, c1);
		return;
	}
	
	int cx = T; anti[cx] = true;
	while (true) {
		cx = par[cx];
		anti[cx] = true;
		if (cx == c1) break;
	}
	
	vector<int> V2;
	for (int i = c1 + 1; i < N; i++) {
		if (dist[i] == cand_dst && anti[i] == false) V2.push_back(i);
	}
	
	// ----------------------------- 6. Find S --------------------------------
	int c3 = 0;
	for (int i = 16; i >= 0; i--) {
		for (int j = 0; j < W.size(); j++) W[j] = 1;
		for (int j = c1 + 1; j < W.size(); j++) W[paredge[j]] = 0;
		
		for (int j = 0; j < c3 + (1 << i); j++) {
			if (j >= V2.size()) break;
			W[paredge[V2[j]]] = 1;
		}
		long long p3 = ask(W);
		if (p3 == BASE) c3 += (1 << i);
	}
	
	long long S = V2[c3];
	answer(S, T);
	return;
}

Compilation message

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < GG[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < UU.size(); i++) {
                   ~~^~~~~~~~~~~
highway.cpp:33:3: 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:33:45: 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:34:3: 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:34:45: 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:44:22: 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:60:22: 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; }
                    ~~^~~~~~~~~~
highway.cpp:126:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[pos1].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
highway.cpp:136:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < G[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
highway.cpp:154:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < W.size(); j++) W[j] = 1;
                   ~~^~~~~~~~~~
highway.cpp:156:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j >= V.size()) break;
        ~~^~~~~~~~~~~
highway.cpp:185:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < W.size(); j++) W[j] = 1;
                   ~~^~~~~~~~~~
highway.cpp:186:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = c1 + 1; j < W.size(); j++) W[paredge[j]] = 0;
                        ~~^~~~~~~~~~
highway.cpp:189:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j >= V2.size()) break;
        ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12664 KB Output is correct
2 Correct 14 ms 12664 KB Output is correct
3 Correct 14 ms 12664 KB Output is correct
4 Correct 14 ms 12668 KB Output is correct
5 Correct 14 ms 12616 KB Output is correct
6 Correct 14 ms 12664 KB Output is correct
7 Correct 14 ms 12764 KB Output is correct
8 Correct 14 ms 12680 KB Output is correct
9 Correct 14 ms 12676 KB Output is correct
10 Correct 14 ms 12680 KB Output is correct
11 Correct 14 ms 12756 KB Output is correct
12 Correct 14 ms 12684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12840 KB Output is correct
2 Correct 49 ms 14712 KB Output is correct
3 Correct 512 ms 30840 KB Output is correct
4 Correct 568 ms 30792 KB Output is correct
5 Correct 484 ms 30804 KB Output is correct
6 Correct 482 ms 30828 KB Output is correct
7 Correct 495 ms 30832 KB Output is correct
8 Correct 496 ms 30828 KB Output is correct
9 Correct 484 ms 30820 KB Output is correct
10 Correct 527 ms 30824 KB Output is correct
11 Correct 526 ms 32436 KB Output is correct
12 Correct 556 ms 33192 KB Output is correct
13 Correct 535 ms 32692 KB Output is correct
14 Correct 559 ms 31924 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15548 KB Output is correct
2 Correct 89 ms 18368 KB Output is correct
3 Correct 97 ms 21052 KB Output is correct
4 Correct 270 ms 37688 KB Output is correct
5 Correct 246 ms 37772 KB Output is correct
6 Correct 263 ms 37792 KB Output is correct
7 Correct 257 ms 37768 KB Output is correct
8 Correct 294 ms 37784 KB Output is correct
9 Correct 270 ms 37720 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12920 KB Output is correct
2 Correct 50 ms 14760 KB Output is correct
3 Correct 363 ms 27144 KB Output is correct
4 Correct 517 ms 30824 KB Output is correct
5 Correct 484 ms 30788 KB Output is correct
6 Correct 591 ms 30820 KB Output is correct
7 Correct 505 ms 30920 KB Output is correct
8 Correct 485 ms 30792 KB Output is correct
9 Correct 502 ms 30752 KB Output is correct
10 Correct 558 ms 30820 KB Output is correct
11 Correct 562 ms 31764 KB Output is correct
12 Correct 551 ms 33296 KB Output is correct
13 Correct 559 ms 32608 KB Output is correct
14 Correct 564 ms 33228 KB Output is correct
15 Correct 491 ms 30824 KB Output is correct
16 Correct 496 ms 30860 KB Output is correct
17 Correct 549 ms 32988 KB Output is correct
18 Correct 554 ms 32308 KB Output is correct
19 Correct 509 ms 30868 KB Output is correct
20 Correct 542 ms 33820 KB Output is correct
21 Correct 412 ms 31532 KB Output is correct
22 Correct 433 ms 31524 KB Output is correct
23 Correct 443 ms 31272 KB Output is correct
24 Correct 464 ms 31912 KB Output is correct
25 Correct 560 ms 36648 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13684 KB Output is correct
2 Correct 42 ms 13688 KB Output is correct
3 Correct 265 ms 20920 KB Output is correct
4 Correct 281 ms 20888 KB Output is correct
5 Correct 318 ms 22180 KB Output is correct
6 Correct 321 ms 21736 KB Output is correct
7 Correct 337 ms 22040 KB Output is correct
8 Correct 345 ms 22328 KB Output is correct
9 Correct 243 ms 17580 KB Output is correct
10 Correct 229 ms 17512 KB Output is correct
11 Correct 237 ms 16976 KB Output is correct
12 Correct 307 ms 20660 KB Output is correct
13 Correct 299 ms 22444 KB Output is correct
14 Correct 323 ms 22092 KB Output is correct
15 Correct 341 ms 22104 KB Output is correct
16 Correct 288 ms 20976 KB Output is correct
17 Correct 219 ms 21028 KB Output is correct
18 Correct 245 ms 20572 KB Output is correct
19 Correct 231 ms 21060 KB Output is correct
20 Correct 228 ms 20004 KB Output is correct
21 Correct 363 ms 22788 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Partially correct 49 ms 13712 KB Output is partially correct
2 Partially correct 42 ms 13680 KB Output is partially correct
3 Partially correct 250 ms 20448 KB Output is partially correct
4 Partially correct 261 ms 21052 KB Output is partially correct
5 Partially correct 284 ms 20728 KB Output is partially correct
6 Partially correct 316 ms 22460 KB Output is partially correct
7 Partially correct 228 ms 20652 KB Output is partially correct
8 Correct 253 ms 21312 KB Output is correct
9 Correct 246 ms 21696 KB Output is correct
10 Partially correct 338 ms 22708 KB Output is partially correct
11 Partially correct 310 ms 21856 KB Output is partially correct
12 Partially correct 331 ms 22820 KB Output is partially correct
13 Correct 258 ms 17528 KB Output is correct
14 Correct 217 ms 20528 KB Output is correct
15 Correct 225 ms 18992 KB Output is correct
16 Correct 218 ms 18608 KB Output is correct
17 Correct 242 ms 16824 KB Output is correct
18 Correct 254 ms 19116 KB Output is correct
19 Partially correct 317 ms 21280 KB Output is partially correct
20 Partially correct 328 ms 21892 KB Output is partially correct
21 Partially correct 321 ms 21772 KB Output is partially correct
22 Partially correct 325 ms 21516 KB Output is partially correct
23 Partially correct 334 ms 22564 KB Output is partially correct
24 Partially correct 356 ms 22376 KB Output is partially correct
25 Partially correct 289 ms 19852 KB Output is partially correct
26 Partially correct 309 ms 22792 KB Output is partially correct
27 Partially correct 226 ms 19956 KB Output is partially correct
28 Correct 222 ms 19916 KB Output is correct
29 Partially correct 239 ms 19708 KB Output is partially correct
30 Partially correct 221 ms 18852 KB Output is partially correct
31 Partially correct 217 ms 20640 KB Output is partially correct
32 Partially correct 227 ms 19512 KB Output is partially correct
33 Partially correct 168 ms 20512 KB Output is partially correct
34 Correct 196 ms 21052 KB Output is correct
35 Partially correct 234 ms 21180 KB Output is partially correct
36 Partially correct 218 ms 19740 KB Output is partially correct
37 Partially correct 230 ms 20196 KB Output is partially correct
38 Partially correct 244 ms 19140 KB Output is partially correct
39 Partially correct 339 ms 22852 KB Output is partially correct
40 Partially correct 333 ms 22836 KB Output is partially correct
41 Partially correct 377 ms 22748 KB Output is partially correct
42 Partially correct 333 ms 22780 KB Output is partially correct