oj.uz

Submission #139104

# Submission time Handle Problem Language Result Execution time Memory
139104 2019-07-31T09:29:55 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 292 ms 9328 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 & 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 , edge1);
	int T = finder(V2 , edge2);

	if (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 376 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 324 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 2 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 476 KB Output is correct
2 Correct 40 ms 1248 KB Output is correct
3 Correct 237 ms 9016 KB Output is correct
4 Correct 245 ms 9132 KB Output is correct
5 Correct 228 ms 9008 KB Output is correct
6 Correct 236 ms 8988 KB Output is correct
7 Correct 232 ms 9004 KB Output is correct
8 Correct 216 ms 9000 KB Output is correct
9 Correct 227 ms 8980 KB Output is correct
10 Correct 225 ms 9012 KB Output is correct
11 Correct 222 ms 8912 KB Output is correct
12 Correct 275 ms 8900 KB Output is correct
13 Correct 263 ms 8900 KB Output is correct
14 Correct 269 ms 8904 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1364 KB Output is correct
2 Correct 40 ms 2276 KB Output is correct
3 Correct 69 ms 3228 KB Output is correct
4 Correct 199 ms 8840 KB Output is correct
5 Correct 190 ms 8892 KB Output is correct
6 Correct 177 ms 8988 KB Output is correct
7 Correct 158 ms 8988 KB Output is correct
8 Correct 187 ms 8900 KB Output is correct
9 Correct 195 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 16 ms 1312 KB Output is correct
3 Correct 156 ms 7188 KB Output is correct
4 Correct 216 ms 8992 KB Output is correct
5 Correct 202 ms 9028 KB Output is correct
6 Correct 197 ms 9008 KB Output is correct
7 Correct 180 ms 9012 KB Output is correct
8 Correct 207 ms 9104 KB Output is correct
9 Correct 237 ms 8996 KB Output is correct
10 Correct 217 ms 9004 KB Output is correct
11 Correct 292 ms 8908 KB Output is correct
12 Correct 247 ms 8936 KB Output is correct
13 Correct 267 ms 8892 KB Output is correct
14 Correct 241 ms 8920 KB Output is correct
15 Correct 234 ms 8992 KB Output is correct
16 Correct 222 ms 8996 KB Output is correct
17 Correct 245 ms 8896 KB Output is correct
18 Correct 253 ms 8908 KB Output is correct
19 Correct 226 ms 8956 KB Output is correct
20 Correct 234 ms 8900 KB Output is correct
21 Correct 197 ms 9280 KB Output is correct
22 Correct 194 ms 9328 KB Output is correct
23 Correct 177 ms 9244 KB Output is correct
24 Correct 235 ms 9196 KB Output is correct
25 Correct 259 ms 9004 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 2552 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 Incorrect 28 ms 1288 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -