oj.uz

Submission #139057

# Submission time Handle Problem Language Result Execution time Memory
139057 2019-07-31T08:52:05 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 313 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;

	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 (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 = 1ll * len * B;

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

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

			if (ask(local) == len2) hi = mid;
			else lo = mid;
		}
		if (hi == -1) 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:112: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 248 KB Output is correct
2 Correct 3 ms 304 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 2 ms 248 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 248 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 376 KB Output is correct
12 Correct 2 ms 420 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 472 KB Output is correct
2 Correct 20 ms 1284 KB Output is correct
3 Correct 210 ms 9008 KB Output is correct
4 Correct 223 ms 9008 KB Output is correct
5 Correct 227 ms 9008 KB Output is correct
6 Correct 219 ms 9012 KB Output is correct
7 Correct 226 ms 9008 KB Output is correct
8 Correct 242 ms 9004 KB Output is correct
9 Correct 223 ms 9004 KB Output is correct
10 Correct 245 ms 8996 KB Output is correct
11 Correct 255 ms 8892 KB Output is correct
12 Correct 239 ms 8904 KB Output is correct
13 Correct 313 ms 8896 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 19 ms 1252 KB Output is correct
2 Correct 65 ms 2208 KB Output is correct
3 Correct 60 ms 3208 KB Output is correct
4 Correct 171 ms 8900 KB Output is correct
5 Correct 180 ms 8900 KB Output is correct
6 Correct 168 ms 8900 KB Output is correct
7 Correct 171 ms 8992 KB Output is correct
8 Correct 170 ms 8936 KB Output is correct
9 Correct 172 ms 9004 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 16 ms 1252 KB Output is correct
3 Correct 165 ms 7368 KB Output is correct
4 Correct 214 ms 9000 KB Output is correct
5 Correct 221 ms 9000 KB Output is correct
6 Correct 239 ms 9000 KB Output is correct
7 Correct 207 ms 8996 KB Output is correct
8 Correct 218 ms 8940 KB Output is correct
9 Correct 239 ms 9012 KB Output is correct
10 Correct 250 ms 9000 KB Output is correct
11 Correct 246 ms 8848 KB Output is correct
12 Correct 238 ms 8908 KB Output is correct
13 Correct 258 ms 8916 KB Output is correct
14 Correct 308 ms 8904 KB Output is correct
15 Correct 227 ms 9000 KB Output is correct
16 Correct 191 ms 9068 KB Output is correct
17 Correct 227 ms 8904 KB Output is correct
18 Correct 224 ms 8944 KB Output is correct
19 Correct 209 ms 9096 KB Output is correct
20 Correct 234 ms 8964 KB Output is correct
21 Correct 139 ms 9264 KB Output is correct
22 Correct 162 ms 9340 KB Output is correct
23 Correct 186 ms 9260 KB Output is correct
24 Correct 202 ms 9228 KB Output is correct
25 Correct 215 ms 8952 KB Output is correct

Subtask #5
0 / 18.0

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