oj.uz

Submission #139048

# Submission time Handle Problem Language Result Execution time Memory
139048 2019-07-31T08:38:42 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 278 ms 9320 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;

	auto cnt = [&](vi cond) ->int {
		ll res = ask(cond);
		return (res - 1ll * A * len) / (B - 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();
		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 (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 : [eyd akardan s O t:

	auto finder = [&](int root , vi & edge) {
		int len2 = -1;
		{
			vi local(M);
			for (auto e : edge)
				local[e] = 1;
			len2 = cnt(local);
		}

		if (!len2) return root;

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

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

			if (cnt(local) == len2) hi = mid;
			else lo = mid;
		}
		return U[edge[hi]];
	};

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

	answer(S , T);

	return;


}

Compilation message

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
highway.cpp: In lambda function:
highway.cpp:118: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 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 248 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 252 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 27 ms 1272 KB Output is correct
3 Correct 240 ms 9012 KB Output is correct
4 Correct 261 ms 9012 KB Output is correct
5 Correct 252 ms 9004 KB Output is correct
6 Correct 232 ms 9064 KB Output is correct
7 Correct 247 ms 9004 KB Output is correct
8 Correct 241 ms 9092 KB Output is correct
9 Correct 268 ms 8972 KB Output is correct
10 Correct 244 ms 9024 KB Output is correct
11 Correct 252 ms 8908 KB Output is correct
12 Correct 229 ms 8908 KB Output is correct
13 Correct 254 ms 8864 KB Output is correct
14 Correct 261 ms 8876 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1320 KB Output is correct
2 Correct 35 ms 2288 KB Output is correct
3 Correct 47 ms 3352 KB Output is correct
4 Correct 171 ms 8896 KB Output is correct
5 Correct 186 ms 8900 KB Output is correct
6 Correct 171 ms 8896 KB Output is correct
7 Correct 172 ms 8984 KB Output is correct
8 Correct 159 ms 8856 KB Output is correct
9 Correct 183 ms 8992 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 408 KB Output is correct
2 Correct 24 ms 1272 KB Output is correct
3 Correct 156 ms 7112 KB Output is correct
4 Correct 237 ms 9008 KB Output is correct
5 Correct 228 ms 9012 KB Output is correct
6 Correct 221 ms 9008 KB Output is correct
7 Correct 205 ms 9004 KB Output is correct
8 Correct 230 ms 8976 KB Output is correct
9 Correct 258 ms 9000 KB Output is correct
10 Correct 243 ms 9180 KB Output is correct
11 Correct 274 ms 8876 KB Output is correct
12 Correct 277 ms 8904 KB Output is correct
13 Correct 272 ms 8896 KB Output is correct
14 Correct 246 ms 8908 KB Output is correct
15 Correct 207 ms 9000 KB Output is correct
16 Correct 238 ms 8996 KB Output is correct
17 Correct 251 ms 8904 KB Output is correct
18 Correct 278 ms 9036 KB Output is correct
19 Correct 228 ms 9000 KB Output is correct
20 Correct 251 ms 8880 KB Output is correct
21 Correct 173 ms 9308 KB Output is correct
22 Correct 195 ms 9320 KB Output is correct
23 Correct 198 ms 9252 KB Output is correct
24 Correct 214 ms 9224 KB Output is correct
25 Correct 234 ms 8972 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 2592 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 25 ms 2568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -