oj.uz

Submission #139075

# Submission time Handle Problem Language Result Execution time Memory
139075 2019-07-31T09:01:07 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 349 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;

	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();
		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);

	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:119:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:27:7: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
  auto cnt = [&](vi cond) ->int {
       ^~~

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 408 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 324 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 6 ms 400 KB Output is correct
2 Correct 29 ms 1400 KB Output is correct
3 Correct 239 ms 9004 KB Output is correct
4 Correct 171 ms 9060 KB Output is correct
5 Correct 216 ms 9004 KB Output is correct
6 Correct 220 ms 9020 KB Output is correct
7 Correct 210 ms 8980 KB Output is correct
8 Correct 229 ms 9004 KB Output is correct
9 Correct 193 ms 8988 KB Output is correct
10 Correct 177 ms 8996 KB Output is correct
11 Correct 230 ms 8896 KB Output is correct
12 Correct 294 ms 8892 KB Output is correct
13 Correct 251 ms 8920 KB Output is correct
14 Correct 234 ms 8904 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1240 KB Output is correct
2 Correct 58 ms 2276 KB Output is correct
3 Correct 96 ms 3224 KB Output is correct
4 Correct 223 ms 8900 KB Output is correct
5 Correct 206 ms 8908 KB Output is correct
6 Correct 184 ms 8864 KB Output is correct
7 Correct 135 ms 8988 KB Output is correct
8 Correct 163 ms 8920 KB Output is correct
9 Correct 214 ms 9064 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 404 KB Output is correct
2 Correct 23 ms 1320 KB Output is correct
3 Correct 162 ms 7164 KB Output is correct
4 Correct 206 ms 9016 KB Output is correct
5 Correct 227 ms 8996 KB Output is correct
6 Correct 256 ms 8996 KB Output is correct
7 Correct 302 ms 8988 KB Output is correct
8 Correct 219 ms 8988 KB Output is correct
9 Correct 227 ms 9000 KB Output is correct
10 Correct 240 ms 9000 KB Output is correct
11 Correct 226 ms 8912 KB Output is correct
12 Correct 262 ms 8896 KB Output is correct
13 Correct 206 ms 8908 KB Output is correct
14 Correct 242 ms 8904 KB Output is correct
15 Correct 219 ms 9000 KB Output is correct
16 Correct 199 ms 9008 KB Output is correct
17 Correct 271 ms 8880 KB Output is correct
18 Correct 255 ms 8896 KB Output is correct
19 Correct 250 ms 8960 KB Output is correct
20 Correct 234 ms 8908 KB Output is correct
21 Correct 159 ms 9256 KB Output is correct
22 Correct 206 ms 9332 KB Output is correct
23 Correct 200 ms 9308 KB Output is correct
24 Correct 224 ms 9228 KB Output is correct
25 Correct 349 ms 8944 KB Output is correct

Subtask #5
0 / 18.0

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