oj.uz

Submission #120354

# Submission time Handle Problem Language Result Execution time Memory
120354 2019-06-24T08:48:19 Z 김세빈(#2948) Highway Tolls (IOI18_highway) C++14
90 / 100
 435 ms 11224 KB 
#include <bits/stdc++.h>

#include "highway.h"

using namespace std;

typedef long long ll;

vector <int> G[101010];
queue <int> Q;
int N[101010], D[101010], P[101010];
int cnt;

void dfs(int p)
{
	N[p] = ++cnt;
	
	for(int &t: G[p]){
		if(!N[t]) dfs(t);
	}
}

void bfs(int n, int p)
{
	int i;
	
	for(i=0; i<n; i++){
		N[i] = 0;
	}
	
	cnt = 0; Q.push(p);
	N[p] = ++cnt; D[p] = 0;
	
	for(; !Q.empty(); ){
		p = Q.front(); Q.pop();
		for(int &t: G[p]){
			if(!N[t]){
				P[t] = p; D[t] = D[p] + 1;
				N[t] = ++cnt;
				Q.push(t);
			}
		}
	}
}
void find_pair(int n, vector <int> U, vector <int> V, int a, int b)
{
	int m = U.size();
	vector <int> W(m, 0);
	int i, k, p, u, v, s, e;
	
	for(i=0; i<m; i++){
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	
	k = ask(W) / a;
	
	cnt = 0; dfs(0);
	
	for(s=1, e=n; s<=e; ){
		for(i=0; i<m; i++){
			if(min(N[U[i]], N[V[i]]) <= (s + e >> 1)) W[i] = 1;
			else W[i] = 0;
		}
		if(ask(W) != (ll)a * k) e = (s + e >> 1) - 1;
		else s = (s + e >> 1) + 1;
	}
	
	for(p=0; p<n; p++){
		if(N[p] == e + 1) break;
	}
	
	bfs(n, p);
	
	for(s=1, e=n; s<=e; ){
		for(i=0; i<m; i++){
			if(P[U[i]] != V[i] && P[V[i]] != U[i]) W[i] = 1;
			else if(max(N[U[i]], N[V[i]]) >= (s + e >> 1)) W[i] = 1;
			else W[i] = 0;
		}
		if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
		else e = (s + e >> 1) - 1;
	}
	
	for(u=0; u<n; u++){
		if(N[u] == s - 1) break;
	}
	
	bfs(n, u);
	
	for(i=0, cnt=0; i<n; i++){
		if(D[i] == k) N[i] = ++cnt;
		else N[i] = 0;
	}
	
	for(s=1, e=cnt; s<=e; ){
		for(i=0; i<m; i++){
			if(P[U[i]] != V[i] && P[V[i]] != U[i]) W[i] = 1;
			else if(max(N[U[i]], N[V[i]]) >= (s + e >> 1)) W[i] = 1;
			else W[i] = 0;
		}
		if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
		else e = (s + e >> 1) - 1;
	}
	
	for(v=0; v<n; v++){
		if(N[v] == s - 1) break;
	}
	
	answer(u, v);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:62:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    if(min(N[U[i]], N[V[i]]) <= (s + e >> 1)) W[i] = 1;
                                 ~~^~~
highway.cpp:65:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) e = (s + e >> 1) - 1;
                                ~~^~~
highway.cpp:66:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else s = (s + e >> 1) + 1;
             ~~^~~
highway.cpp:78:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    else if(max(N[U[i]], N[V[i]]) >= (s + e >> 1)) W[i] = 1;
                                      ~~^~~
highway.cpp:81:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
                                ~~^~~
highway.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s + e >> 1) - 1;
             ~~^~~
highway.cpp:99:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    else if(max(N[U[i]], N[V[i]]) >= (s + e >> 1)) W[i] = 1;
                                      ~~^~~
highway.cpp:102:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
                                ~~^~~
highway.cpp:103:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (s + e >> 1) - 1;
             ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2696 KB Output is correct
3 Correct 4 ms 2696 KB Output is correct
4 Correct 4 ms 2600 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2700 KB Output is correct
7 Correct 4 ms 2696 KB Output is correct
8 Correct 4 ms 2696 KB Output is correct
9 Correct 4 ms 2700 KB Output is correct
10 Correct 4 ms 2780 KB Output is correct
11 Correct 4 ms 2852 KB Output is correct
12 Correct 4 ms 2776 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2740 KB Output is correct
2 Correct 25 ms 3280 KB Output is correct
3 Correct 254 ms 8504 KB Output is correct
4 Correct 315 ms 8580 KB Output is correct
5 Correct 257 ms 8512 KB Output is correct
6 Correct 262 ms 8532 KB Output is correct
7 Correct 250 ms 8604 KB Output is correct
8 Correct 269 ms 8508 KB Output is correct
9 Correct 250 ms 8584 KB Output is correct
10 Correct 257 ms 8504 KB Output is correct
11 Correct 226 ms 9024 KB Output is correct
12 Correct 263 ms 9320 KB Output is correct
13 Correct 251 ms 9084 KB Output is correct
14 Correct 271 ms 8832 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3556 KB Output is correct
2 Correct 42 ms 4568 KB Output is correct
3 Correct 47 ms 5512 KB Output is correct
4 Correct 152 ms 11156 KB Output is correct
5 Correct 134 ms 11168 KB Output is correct
6 Correct 117 ms 11172 KB Output is correct
7 Correct 137 ms 11172 KB Output is correct
8 Correct 165 ms 11168 KB Output is correct
9 Correct 174 ms 11168 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2756 KB Output is correct
2 Correct 22 ms 3260 KB Output is correct
3 Correct 137 ms 7232 KB Output is correct
4 Correct 221 ms 8500 KB Output is correct
5 Correct 211 ms 8492 KB Output is correct
6 Correct 232 ms 8516 KB Output is correct
7 Correct 252 ms 8604 KB Output is correct
8 Correct 220 ms 8504 KB Output is correct
9 Correct 210 ms 8496 KB Output is correct
10 Correct 240 ms 8612 KB Output is correct
11 Correct 228 ms 8788 KB Output is correct
12 Correct 250 ms 9376 KB Output is correct
13 Correct 262 ms 9140 KB Output is correct
14 Correct 250 ms 9456 KB Output is correct
15 Correct 223 ms 8608 KB Output is correct
16 Correct 199 ms 8500 KB Output is correct
17 Correct 213 ms 9220 KB Output is correct
18 Correct 289 ms 9016 KB Output is correct
19 Correct 235 ms 8516 KB Output is correct
20 Correct 240 ms 9596 KB Output is correct
21 Correct 206 ms 9192 KB Output is correct
22 Correct 192 ms 9232 KB Output is correct
23 Correct 219 ms 9028 KB Output is correct
24 Correct 213 ms 9144 KB Output is correct
25 Correct 284 ms 10752 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3332 KB Output is correct
2 Correct 32 ms 3392 KB Output is correct
3 Correct 261 ms 9320 KB Output is correct
4 Correct 319 ms 9956 KB Output is correct
5 Correct 384 ms 10748 KB Output is correct
6 Correct 353 ms 10840 KB Output is correct
7 Correct 386 ms 10832 KB Output is correct
8 Correct 329 ms 10780 KB Output is correct
9 Correct 217 ms 7384 KB Output is correct
10 Correct 202 ms 7808 KB Output is correct
11 Correct 283 ms 7852 KB Output is correct
12 Correct 355 ms 10220 KB Output is correct
13 Correct 342 ms 10528 KB Output is correct
14 Correct 399 ms 11112 KB Output is correct
15 Correct 396 ms 11128 KB Output is correct
16 Correct 305 ms 9224 KB Output is correct
17 Correct 261 ms 9220 KB Output is correct
18 Correct 241 ms 9356 KB Output is correct
19 Correct 269 ms 9172 KB Output is correct
20 Correct 238 ms 9260 KB Output is correct
21 Correct 356 ms 10400 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3328 KB Output is correct
2 Correct 29 ms 3384 KB Output is correct
3 Correct 291 ms 9480 KB Output is correct
4 Correct 338 ms 9716 KB Output is correct
5 Correct 309 ms 9880 KB Output is correct
6 Correct 435 ms 10832 KB Output is correct
7 Correct 305 ms 9476 KB Output is correct
8 Correct 314 ms 9692 KB Output is correct
9 Correct 323 ms 9960 KB Output is correct
10 Correct 383 ms 10752 KB Output is correct
11 Correct 406 ms 10768 KB Output is correct
12 Correct 379 ms 10744 KB Output is correct
13 Correct 265 ms 7848 KB Output is correct
14 Correct 265 ms 7716 KB Output is correct
15 Correct 242 ms 7916 KB Output is correct
16 Correct 244 ms 7796 KB Output is correct
17 Correct 299 ms 7852 KB Output is correct
18 Correct 272 ms 7672 KB Output is correct
19 Correct 393 ms 10480 KB Output is correct
20 Correct 374 ms 10848 KB Output is correct
21 Correct 405 ms 11224 KB Output is correct
22 Correct 384 ms 11192 KB Output is correct
23 Correct 344 ms 11108 KB Output is correct
24 Correct 383 ms 11112 KB Output is correct
25 Correct 358 ms 11084 KB Output is correct
26 Correct 328 ms 11116 KB Output is correct
27 Correct 235 ms 9236 KB Output is correct
28 Partially correct 243 ms 9160 KB Output is partially correct
29 Correct 210 ms 9400 KB Output is correct
30 Correct 231 ms 9252 KB Output is correct
31 Partially correct 245 ms 9224 KB Output is partially correct
32 Partially correct 312 ms 9152 KB Output is partially correct
33 Correct 277 ms 9416 KB Output is correct
34 Partially correct 254 ms 9228 KB Output is partially correct
35 Correct 204 ms 9212 KB Output is correct
36 Correct 208 ms 9196 KB Output is correct
37 Partially correct 254 ms 9304 KB Output is partially correct
38 Partially correct 232 ms 9220 KB Output is partially correct
39 Correct 317 ms 10168 KB Output is correct
40 Correct 288 ms 10324 KB Output is correct
41 Correct 277 ms 10364 KB Output is correct
42 Correct 349 ms 10140 KB Output is correct