oj.uz

Submission #139082

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

	// 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:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
highway.cpp: In lambda function:
highway.cpp:111: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 324 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 2 ms 324 KB Output is correct
5 Correct 2 ms 296 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 328 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 3 ms 296 KB Output is correct
2 Correct 24 ms 1320 KB Output is correct
3 Correct 228 ms 8992 KB Output is correct
4 Correct 211 ms 9008 KB Output is correct
5 Correct 204 ms 8988 KB Output is correct
6 Correct 305 ms 9004 KB Output is correct
7 Correct 242 ms 8988 KB Output is correct
8 Correct 217 ms 9008 KB Output is correct
9 Correct 215 ms 8960 KB Output is correct
10 Correct 256 ms 8988 KB Output is correct
11 Correct 229 ms 8900 KB Output is correct
12 Correct 234 ms 8896 KB Output is correct
13 Correct 247 ms 8964 KB Output is correct
14 Correct 251 ms 8900 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1240 KB Output is correct
2 Correct 42 ms 2280 KB Output is correct
3 Correct 48 ms 3224 KB Output is correct
4 Correct 208 ms 8892 KB Output is correct
5 Correct 161 ms 8912 KB Output is correct
6 Correct 181 ms 8912 KB Output is correct
7 Correct 197 ms 8992 KB Output is correct
8 Correct 163 ms 8876 KB Output is correct
9 Correct 197 ms 8992 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 480 KB Output is correct
2 Correct 25 ms 1272 KB Output is correct
3 Correct 187 ms 7200 KB Output is correct
4 Correct 218 ms 9032 KB Output is correct
5 Correct 200 ms 9016 KB Output is correct
6 Correct 219 ms 8984 KB Output is correct
7 Correct 209 ms 8980 KB Output is correct
8 Correct 185 ms 8984 KB Output is correct
9 Correct 229 ms 9000 KB Output is correct
10 Correct 237 ms 9016 KB Output is correct
11 Correct 262 ms 8852 KB Output is correct
12 Correct 258 ms 8928 KB Output is correct
13 Correct 247 ms 8900 KB Output is correct
14 Correct 249 ms 8900 KB Output is correct
15 Correct 222 ms 9004 KB Output is correct
16 Correct 213 ms 9048 KB Output is correct
17 Correct 251 ms 8896 KB Output is correct
18 Correct 249 ms 8904 KB Output is correct
19 Correct 213 ms 8996 KB Output is correct
20 Correct 241 ms 8896 KB Output is correct
21 Correct 177 ms 9236 KB Output is correct
22 Correct 177 ms 9348 KB Output is correct
23 Correct 200 ms 9244 KB Output is correct
24 Correct 204 ms 9220 KB Output is correct
25 Correct 244 ms 8960 KB Output is correct

Subtask #5
0 / 18.0

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