oj.uz

Submission #139053

# Submission time Handle Problem Language Result Execution time Memory
139053 2019-07-31T08:46:50 Z MAMBA Highway Tolls (IOI18_highway) C++17
51 / 100
 323 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();
		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) {
		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:120: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 328 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 1 ms 248 KB Output is correct
4 Correct 2 ms 376 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 376 KB Output is correct
8 Correct 3 ms 248 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 248 KB Output is correct
11 Correct 2 ms 268 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 4 ms 376 KB Output is correct
2 Correct 24 ms 1272 KB Output is correct
3 Correct 232 ms 9004 KB Output is correct
4 Correct 251 ms 8996 KB Output is correct
5 Correct 233 ms 9068 KB Output is correct
6 Correct 206 ms 8996 KB Output is correct
7 Correct 244 ms 9004 KB Output is correct
8 Correct 215 ms 8984 KB Output is correct
9 Correct 229 ms 9008 KB Output is correct
10 Correct 249 ms 9008 KB Output is correct
11 Correct 273 ms 8864 KB Output is correct
12 Correct 277 ms 8880 KB Output is correct
13 Correct 276 ms 8912 KB Output is correct
14 Correct 287 ms 8896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1400 KB Output is correct
2 Correct 31 ms 2276 KB Output is correct
3 Correct 44 ms 3328 KB Output is correct
4 Correct 178 ms 8904 KB Output is correct
5 Correct 164 ms 8880 KB Output is correct
6 Correct 191 ms 8904 KB Output is correct
7 Correct 157 ms 8980 KB Output is correct
8 Correct 186 ms 8952 KB Output is correct
9 Correct 164 ms 8980 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 396 KB Output is correct
2 Correct 24 ms 1384 KB Output is correct
3 Correct 149 ms 7236 KB Output is correct
4 Correct 217 ms 9000 KB Output is correct
5 Correct 253 ms 9000 KB Output is correct
6 Correct 208 ms 9000 KB Output is correct
7 Correct 223 ms 8936 KB Output is correct
8 Correct 224 ms 9004 KB Output is correct
9 Correct 274 ms 9012 KB Output is correct
10 Correct 252 ms 9048 KB Output is correct
11 Correct 240 ms 8900 KB Output is correct
12 Correct 253 ms 8904 KB Output is correct
13 Correct 251 ms 8920 KB Output is correct
14 Correct 323 ms 8900 KB Output is correct
15 Correct 219 ms 9000 KB Output is correct
16 Correct 238 ms 9008 KB Output is correct
17 Correct 247 ms 8864 KB Output is correct
18 Correct 257 ms 8888 KB Output is correct
19 Correct 224 ms 8960 KB Output is correct
20 Correct 240 ms 8908 KB Output is correct
21 Correct 241 ms 9288 KB Output is correct
22 Correct 191 ms 9332 KB Output is correct
23 Correct 260 ms 9252 KB Output is correct
24 Correct 199 ms 9220 KB Output is correct
25 Correct 265 ms 9096 KB Output is correct

Subtask #5
0 / 18.0

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