oj.uz

Submission #120309

# Submission time Handle Problem Language Result Execution time Memory
120309 2019-06-24T07:14:55 Z 김세빈(#2948) Highway Tolls (IOI18_highway) C++14
51 / 100
 295 ms 11264 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(max(N[U[i]], N[V[i]]) >= (s + e >> 1)) W[i] = 1;
			else W[i] = 0;
		}
		if(ask(W) == (ll)b * k) s = (s + e >> 1) + 1;
		else e = (s + e >> 1) - 1;
	}
	
	for(p=0; p<n; p++){
		if(N[p] == s - 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(max(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)b * k) s = (s + e >> 1) + 1;
                                ~~^~~
highway.cpp:66:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else e = (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 4 ms 2696 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2696 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 14 ms 2704 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 2704 KB Output is correct
10 Correct 5 ms 2680 KB Output is correct
11 Correct 4 ms 2696 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 2708 KB Output is correct
2 Correct 23 ms 3300 KB Output is correct
3 Correct 256 ms 8596 KB Output is correct
4 Correct 257 ms 8508 KB Output is correct
5 Correct 272 ms 8536 KB Output is correct
6 Correct 249 ms 8604 KB Output is correct
7 Correct 270 ms 8620 KB Output is correct
8 Correct 293 ms 8500 KB Output is correct
9 Correct 235 ms 8512 KB Output is correct
10 Correct 260 ms 8516 KB Output is correct
11 Correct 272 ms 9024 KB Output is correct
12 Correct 273 ms 9324 KB Output is correct
13 Correct 269 ms 9096 KB Output is correct
14 Correct 223 ms 8828 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3548 KB Output is correct
2 Correct 73 ms 4584 KB Output is correct
3 Correct 61 ms 5508 KB Output is correct
4 Correct 166 ms 11264 KB Output is correct
5 Correct 116 ms 11160 KB Output is correct
6 Correct 128 ms 11172 KB Output is correct
7 Correct 162 ms 11160 KB Output is correct
8 Correct 135 ms 11164 KB Output is correct
9 Correct 153 ms 11256 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2812 KB Output is correct
2 Correct 25 ms 3256 KB Output is correct
3 Correct 185 ms 7256 KB Output is correct
4 Correct 248 ms 8588 KB Output is correct
5 Correct 231 ms 8496 KB Output is correct
6 Correct 227 ms 8492 KB Output is correct
7 Correct 207 ms 8592 KB Output is correct
8 Correct 225 ms 8512 KB Output is correct
9 Correct 234 ms 8624 KB Output is correct
10 Correct 274 ms 8520 KB Output is correct
11 Correct 281 ms 8764 KB Output is correct
12 Correct 259 ms 9444 KB Output is correct
13 Correct 246 ms 9136 KB Output is correct
14 Correct 279 ms 9380 KB Output is correct
15 Correct 248 ms 8600 KB Output is correct
16 Correct 246 ms 8528 KB Output is correct
17 Correct 271 ms 9204 KB Output is correct
18 Correct 282 ms 9012 KB Output is correct
19 Correct 243 ms 8512 KB Output is correct
20 Correct 295 ms 9588 KB Output is correct
21 Correct 231 ms 9120 KB Output is correct
22 Correct 209 ms 9096 KB Output is correct
23 Correct 290 ms 9036 KB Output is correct
24 Correct 250 ms 9184 KB Output is correct
25 Correct 279 ms 10884 KB Output is correct

Subtask #5
0 / 18.0

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