oj.uz

Submission #139046

# Submission time Handle Problem Language Result Execution time Memory
139046 2019-07-31T08:36:51 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 291 ms 9336 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 408 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 248 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 2 ms 404 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 408 KB Output is correct
11 Correct 2 ms 376 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 25 ms 1272 KB Output is correct
3 Correct 222 ms 9008 KB Output is correct
4 Correct 258 ms 9008 KB Output is correct
5 Correct 272 ms 9032 KB Output is correct
6 Correct 235 ms 9004 KB Output is correct
7 Correct 244 ms 9020 KB Output is correct
8 Correct 238 ms 9012 KB Output is correct
9 Correct 234 ms 9012 KB Output is correct
10 Correct 264 ms 9008 KB Output is correct
11 Correct 245 ms 8900 KB Output is correct
12 Correct 262 ms 8956 KB Output is correct
13 Correct 291 ms 8908 KB Output is correct
14 Correct 259 ms 8928 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1284 KB Output is correct
2 Correct 39 ms 2264 KB Output is correct
3 Correct 67 ms 3336 KB Output is correct
4 Correct 170 ms 8900 KB Output is correct
5 Correct 183 ms 8868 KB Output is correct
6 Correct 185 ms 8904 KB Output is correct
7 Correct 127 ms 8980 KB Output is correct
8 Correct 192 ms 8892 KB Output is correct
9 Correct 164 ms 9092 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 25 ms 1272 KB Output is correct
3 Correct 154 ms 7296 KB Output is correct
4 Correct 220 ms 9036 KB Output is correct
5 Correct 255 ms 8996 KB Output is correct
6 Correct 188 ms 9028 KB Output is correct
7 Correct 222 ms 8984 KB Output is correct
8 Correct 212 ms 8980 KB Output is correct
9 Correct 260 ms 9064 KB Output is correct
10 Correct 245 ms 9004 KB Output is correct
11 Correct 275 ms 8908 KB Output is correct
12 Correct 276 ms 8904 KB Output is correct
13 Correct 272 ms 8908 KB Output is correct
14 Correct 260 ms 8888 KB Output is correct
15 Correct 223 ms 8996 KB Output is correct
16 Correct 221 ms 9080 KB Output is correct
17 Correct 274 ms 8920 KB Output is correct
18 Correct 261 ms 8904 KB Output is correct
19 Correct 247 ms 9012 KB Output is correct
20 Correct 233 ms 8900 KB Output is correct
21 Correct 204 ms 9256 KB Output is correct
22 Correct 206 ms 9336 KB Output is correct
23 Correct 218 ms 9256 KB Output is correct
24 Correct 237 ms 9316 KB Output is correct
25 Correct 256 ms 8944 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 1280 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 22 ms 1336 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -