oj.uz

Submission #120312

# Submission time Handle Problem Language Result Execution time Memory
120312 2019-06-24T07:19:25 Z 김세빈(#2948) Highway Tolls (IOI18_highway) C++14
90 / 100
 417 ms 11268 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;		
//			printf("%d %d %d %d\n", N[U[i]], N[V[i]], max(N[U[i]], N[V[i]]), (s + e >> 1));
		}
//		for(i=0; i<m; i++) printf("%d", W[i]); printf("\n");
//		printf("%lld %d %d %d\n", ask(W), s, e, s + e >> 1);
		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:105:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(ask(W) != (ll)a * k) s = (s + e >> 1) + 1;
                                ~~^~~
highway.cpp:106: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 6 ms 2680 KB Output is correct
2 Correct 4 ms 2696 KB Output is correct
3 Correct 4 ms 2700 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2784 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2700 KB Output is correct
10 Correct 4 ms 2696 KB Output is correct
11 Correct 4 ms 2692 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 27 ms 3320 KB Output is correct
3 Correct 263 ms 8576 KB Output is correct
4 Correct 269 ms 8508 KB Output is correct
5 Correct 266 ms 8616 KB Output is correct
6 Correct 237 ms 8496 KB Output is correct
7 Correct 226 ms 8492 KB Output is correct
8 Correct 263 ms 8520 KB Output is correct
9 Correct 244 ms 8524 KB Output is correct
10 Correct 262 ms 8512 KB Output is correct
11 Correct 273 ms 9020 KB Output is correct
12 Correct 270 ms 9336 KB Output is correct
13 Correct 279 ms 9092 KB Output is correct
14 Correct 287 ms 8832 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3624 KB Output is correct
2 Correct 41 ms 4572 KB Output is correct
3 Correct 59 ms 5512 KB Output is correct
4 Correct 169 ms 11164 KB Output is correct
5 Correct 178 ms 11268 KB Output is correct
6 Correct 161 ms 11156 KB Output is correct
7 Correct 156 ms 11176 KB Output is correct
8 Correct 148 ms 11164 KB Output is correct
9 Correct 176 ms 11164 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2748 KB Output is correct
2 Correct 26 ms 3248 KB Output is correct
3 Correct 183 ms 7232 KB Output is correct
4 Correct 237 ms 8500 KB Output is correct
5 Correct 234 ms 8504 KB Output is correct
6 Correct 241 ms 8496 KB Output is correct
7 Correct 269 ms 8540 KB Output is correct
8 Correct 255 ms 8484 KB Output is correct
9 Correct 244 ms 8500 KB Output is correct
10 Correct 278 ms 8548 KB Output is correct
11 Correct 259 ms 8764 KB Output is correct
12 Correct 306 ms 9380 KB Output is correct
13 Correct 250 ms 9180 KB Output is correct
14 Correct 242 ms 9348 KB Output is correct
15 Correct 217 ms 8596 KB Output is correct
16 Correct 236 ms 8508 KB Output is correct
17 Correct 267 ms 9248 KB Output is correct
18 Correct 260 ms 9024 KB Output is correct
19 Correct 247 ms 8612 KB Output is correct
20 Correct 266 ms 9592 KB Output is correct
21 Correct 241 ms 9192 KB Output is correct
22 Correct 225 ms 9196 KB Output is correct
23 Correct 233 ms 9084 KB Output is correct
24 Correct 246 ms 9264 KB Output is correct
25 Correct 280 ms 10776 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3332 KB Output is correct
2 Correct 28 ms 3384 KB Output is correct
3 Correct 309 ms 9404 KB Output is correct
4 Correct 372 ms 9868 KB Output is correct
5 Correct 388 ms 10812 KB Output is correct
6 Correct 345 ms 10756 KB Output is correct
7 Correct 417 ms 10748 KB Output is correct
8 Correct 373 ms 10752 KB Output is correct
9 Correct 247 ms 7384 KB Output is correct
10 Correct 262 ms 7804 KB Output is correct
11 Correct 300 ms 7844 KB Output is correct
12 Correct 349 ms 10280 KB Output is correct
13 Correct 387 ms 10508 KB Output is correct
14 Correct 394 ms 11104 KB Output is correct
15 Correct 398 ms 11092 KB Output is correct
16 Correct 263 ms 9124 KB Output is correct
17 Correct 221 ms 9228 KB Output is correct
18 Correct 237 ms 9380 KB Output is correct
19 Correct 201 ms 9160 KB Output is correct
20 Correct 259 ms 9356 KB Output is correct
21 Correct 280 ms 10372 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3332 KB Output is correct
2 Correct 60 ms 3384 KB Output is correct
3 Correct 305 ms 9384 KB Output is correct
4 Correct 337 ms 9616 KB Output is correct
5 Correct 342 ms 9872 KB Output is correct
6 Correct 386 ms 10744 KB Output is correct
7 Correct 299 ms 9384 KB Output is correct
8 Correct 324 ms 9664 KB Output is correct
9 Correct 324 ms 9948 KB Output is correct
10 Correct 384 ms 10844 KB Output is correct
11 Correct 401 ms 10872 KB Output is correct
12 Correct 371 ms 10840 KB Output is correct
13 Correct 289 ms 7832 KB Output is correct
14 Correct 250 ms 7720 KB Output is correct
15 Correct 286 ms 7892 KB Output is correct
16 Correct 247 ms 7796 KB Output is correct
17 Correct 293 ms 7904 KB Output is correct
18 Correct 285 ms 7696 KB Output is correct
19 Correct 377 ms 10412 KB Output is correct
20 Correct 395 ms 10800 KB Output is correct
21 Correct 409 ms 11140 KB Output is correct
22 Correct 371 ms 11076 KB Output is correct
23 Correct 365 ms 11176 KB Output is correct
24 Correct 403 ms 11108 KB Output is correct
25 Correct 408 ms 11092 KB Output is correct
26 Correct 399 ms 11124 KB Output is correct
27 Correct 240 ms 9304 KB Output is correct
28 Partially correct 252 ms 9156 KB Output is partially correct
29 Correct 269 ms 9320 KB Output is correct
30 Correct 263 ms 9292 KB Output is correct
31 Partially correct 276 ms 9304 KB Output is partially correct
32 Partially correct 251 ms 9140 KB Output is partially correct
33 Correct 251 ms 9404 KB Output is correct
34 Partially correct 250 ms 9324 KB Output is partially correct
35 Correct 267 ms 9196 KB Output is correct
36 Correct 254 ms 9192 KB Output is correct
37 Partially correct 272 ms 9300 KB Output is partially correct
38 Partially correct 289 ms 9236 KB Output is partially correct
39 Correct 322 ms 10140 KB Output is correct
40 Correct 350 ms 10292 KB Output is correct
41 Correct 357 ms 10352 KB Output is correct
42 Correct 349 ms 10120 KB Output is correct