oj.uz

Submission #139122

# Submission time Handle Problem Language Result Execution time Memory
139122 2019-07-31T09:41:10 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 262 ms 9340 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;
		return U[edge[hi]];
	};

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

	if (true) 
		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 248 KB Output is correct
2 Correct 2 ms 408 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 248 KB Output is correct
9 Correct 2 ms 408 KB Output is correct
10 Correct 2 ms 420 KB Output is correct
11 Correct 2 ms 404 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 392 KB Output is correct
2 Correct 20 ms 1284 KB Output is correct
3 Correct 233 ms 9000 KB Output is correct
4 Correct 262 ms 8968 KB Output is correct
5 Correct 230 ms 8948 KB Output is correct
6 Correct 219 ms 8996 KB Output is correct
7 Correct 259 ms 9008 KB Output is correct
8 Correct 198 ms 8996 KB Output is correct
9 Correct 212 ms 9000 KB Output is correct
10 Correct 235 ms 9000 KB Output is correct
11 Correct 246 ms 8908 KB Output is correct
12 Correct 247 ms 8900 KB Output is correct
13 Correct 232 ms 9008 KB Output is correct
14 Correct 248 ms 8896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1312 KB Output is correct
2 Correct 38 ms 2264 KB Output is correct
3 Correct 48 ms 3236 KB Output is correct
4 Correct 161 ms 8904 KB Output is correct
5 Correct 189 ms 8840 KB Output is correct
6 Correct 157 ms 8896 KB Output is correct
7 Correct 182 ms 9004 KB Output is correct
8 Correct 191 ms 9012 KB Output is correct
9 Correct 156 ms 8984 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 392 KB Output is correct
2 Correct 38 ms 1392 KB Output is correct
3 Correct 148 ms 7232 KB Output is correct
4 Correct 203 ms 9108 KB Output is correct
5 Correct 221 ms 9052 KB Output is correct
6 Correct 178 ms 9036 KB Output is correct
7 Correct 208 ms 9000 KB Output is correct
8 Correct 205 ms 9000 KB Output is correct
9 Correct 206 ms 9004 KB Output is correct
10 Correct 204 ms 9012 KB Output is correct
11 Correct 242 ms 8924 KB Output is correct
12 Correct 260 ms 8900 KB Output is correct
13 Correct 251 ms 8856 KB Output is correct
14 Correct 245 ms 8900 KB Output is correct
15 Correct 223 ms 9012 KB Output is correct
16 Correct 240 ms 9004 KB Output is correct
17 Correct 221 ms 8892 KB Output is correct
18 Correct 255 ms 8900 KB Output is correct
19 Correct 211 ms 8968 KB Output is correct
20 Correct 231 ms 8856 KB Output is correct
21 Correct 180 ms 9264 KB Output is correct
22 Correct 148 ms 9340 KB Output is correct
23 Correct 222 ms 9256 KB Output is correct
24 Correct 206 ms 9236 KB Output is correct
25 Correct 234 ms 8948 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 2496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 2496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -