oj.uz

Submission #139111

# Submission time Handle Problem Language Result Execution time Memory
139111 2019-07-31T09:34:00 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 296 ms 9332 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define all(x) x.begin(),x.end()
#define pb push_back

inline bool smin(int &a , int b) { return b < a ? a = b , true : false; }

typedef vector<int> vi;
typedef long long ll;

void find_pair(int N,  vi U, vi V, int A, int B) {
	int M = U.size();

	vector<vi> adj(N);
	rep(i , 0 , M) {
		adj[U[i]].pb(i);
		adj[V[i]].pb(i);
	}

	// faze 1 : peyda kardan fasele 
	int len = ask(vi(M)) / A;

	// faze 2 : peyda kardane ye yal to masir

	int lovelyEdge = -1;

	{
		int lo = -1 , hi = M - 1;
		while (lo != hi - 1) {
			int mid = lo + hi >> 1;
			vi local(mid + 1 , 1);
			local.resize(M);

			if (ask(local) != 1ll * A * len)
				hi = mid;
			else 
				lo = mid;
		}
		lovelyEdge = hi;
	}


	// faze 3 : peyda kardane rasaye chap va rasaye rast va sakhtane deralht chap o rast :

	vector<bool> active(N , true);
	vi d1(N) , d2(N);
	vi edge1, edge2;
	auto bfs = [&](int v , vi &d, vi& edge) {

		edge.clear();
		edge.pb(lovelyEdge);
		fill(all(d) , 1e9);
		vi q(N);
		int L = 0 , R = 0;

		assert(active[v]);
		d[v] = 0;
		q[R++] = v;
		while (L < R) {
			v = q[L++];		
			for (auto e : adj[v]) {
				int u = V[e] ^ U[e] ^ v;
				if (!active[u]) continue;
				if (smin(d[u] , d[v] + 1)) 
					q[R++] = u;

				if (d[u] == d[v] + 1) {
					if (V[e] == u) 
						swap(U[e] , V[e]);
					edge.pb(e);
				}
			}
		}
		return;
	};

	int V1 = V[lovelyEdge];
	int V2 = U[lovelyEdge];

	bfs(V1 , d1 , edge1);
	bfs(V2 , d2 , edge2);


	fill(all(active) , false);
	rep(i , 0 , N) if (d1[i] < d2[i]) active[i] = true;
	bfs(V1 , d1 , edge1);

	fill(all(active) , false);
	rep(i , 0 , N) if (d2[i] < d1[i]) active[i] = true;
	bfs(V2 , d2 , edge2);


	// faze 4 : peyd akardan s O t:

	auto finder = [&](int root, vi&d ,  vi & edge) {
		ll len2 = -1;

		{
			vi local(M , 1);
			for (auto e : edge) local[e] = 0;
			len2 = ask(local);
		}

		int lo = -1, hi = edge.size() - 1;
		while (lo != hi - 1) {
			int mid = lo + hi >> 1;

			vi local(M , 1);
			rep(i , 0 , mid + 1)
				local[edge[i]] = 0;

			if (ask(local) == len2) hi = mid;
			else lo = mid;
		} 
		if (hi == 0) return root;
		if (d[U[edge[hi]]] <= d[V[edge[hi]]]) assert(0);
		return U[edge[hi]];
	};

	int S = finder(V1 , d1 , edge1);
	int T = finder(V2 , d2 ,edge2);

	if (false && A == 1 && B == 2) 
		assert(d1[S] + 1 + d2[T] <= len);
	
	answer(S , T);

	return;
}

Compilation message

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
highway.cpp: In lambda function:
highway.cpp:110:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 408 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 408 KB Output is correct
11 Correct 3 ms 296 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 472 KB Output is correct
2 Correct 20 ms 1260 KB Output is correct
3 Correct 262 ms 9008 KB Output is correct
4 Correct 235 ms 9016 KB Output is correct
5 Correct 226 ms 8992 KB Output is correct
6 Correct 241 ms 9012 KB Output is correct
7 Correct 243 ms 9016 KB Output is correct
8 Correct 210 ms 8992 KB Output is correct
9 Correct 230 ms 9000 KB Output is correct
10 Correct 233 ms 9040 KB Output is correct
11 Correct 253 ms 8956 KB Output is correct
12 Correct 231 ms 8892 KB Output is correct
13 Correct 226 ms 8896 KB Output is correct
14 Correct 243 ms 8860 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1284 KB Output is correct
2 Correct 37 ms 2300 KB Output is correct
3 Correct 49 ms 3352 KB Output is correct
4 Correct 176 ms 8904 KB Output is correct
5 Correct 169 ms 8908 KB Output is correct
6 Correct 155 ms 8848 KB Output is correct
7 Correct 152 ms 8992 KB Output is correct
8 Correct 228 ms 8888 KB Output is correct
9 Correct 152 ms 8992 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 400 KB Output is correct
2 Correct 46 ms 1264 KB Output is correct
3 Correct 164 ms 7304 KB Output is correct
4 Correct 200 ms 9056 KB Output is correct
5 Correct 203 ms 9060 KB Output is correct
6 Correct 215 ms 8992 KB Output is correct
7 Correct 175 ms 8948 KB Output is correct
8 Correct 211 ms 8956 KB Output is correct
9 Correct 182 ms 9004 KB Output is correct
10 Correct 185 ms 9000 KB Output is correct
11 Correct 257 ms 8932 KB Output is correct
12 Correct 220 ms 8900 KB Output is correct
13 Correct 236 ms 8876 KB Output is correct
14 Correct 235 ms 8852 KB Output is correct
15 Correct 200 ms 9052 KB Output is correct
16 Correct 230 ms 9012 KB Output is correct
17 Correct 210 ms 8860 KB Output is correct
18 Correct 296 ms 8912 KB Output is correct
19 Correct 212 ms 9052 KB Output is correct
20 Correct 230 ms 8912 KB Output is correct
21 Correct 162 ms 9260 KB Output is correct
22 Correct 189 ms 9332 KB Output is correct
23 Correct 197 ms 9260 KB Output is correct
24 Correct 194 ms 9212 KB Output is correct
25 Correct 256 ms 8952 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1340 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 1264 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -