oj.uz

Submission #120307

# Submission time Handle Problem Language Result Execution time Memory
120307 2019-06-24T07:13:51 Z 김세빈(#2948) Highway Tolls (IOI18_highway) C++14
51 / 100
 307 ms 11300 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)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(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)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 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2724 KB Output is correct
4 Correct 4 ms 2692 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2680 KB Output is correct
7 Correct 4 ms 2700 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2700 KB Output is correct
10 Correct 5 ms 2596 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2748 KB Output is correct
2 Correct 38 ms 3356 KB Output is correct
3 Correct 268 ms 8540 KB Output is correct
4 Correct 284 ms 8528 KB Output is correct
5 Correct 277 ms 8564 KB Output is correct
6 Correct 234 ms 8604 KB Output is correct
7 Correct 237 ms 8544 KB Output is correct
8 Correct 260 ms 8568 KB Output is correct
9 Correct 307 ms 8548 KB Output is correct
10 Correct 268 ms 8504 KB Output is correct
11 Correct 275 ms 9028 KB Output is correct
12 Correct 266 ms 9336 KB Output is correct
13 Correct 288 ms 9092 KB Output is correct
14 Correct 271 ms 8836 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3624 KB Output is correct
2 Correct 38 ms 4572 KB Output is correct
3 Correct 53 ms 5516 KB Output is correct
4 Correct 173 ms 11176 KB Output is correct
5 Correct 178 ms 11300 KB Output is correct
6 Correct 149 ms 11184 KB Output is correct
7 Correct 133 ms 11168 KB Output is correct
8 Correct 158 ms 11164 KB Output is correct
9 Correct 177 ms 11160 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 29 ms 3368 KB Output is correct
3 Correct 169 ms 7352 KB Output is correct
4 Correct 265 ms 8500 KB Output is correct
5 Correct 243 ms 8504 KB Output is correct
6 Correct 239 ms 8496 KB Output is correct
7 Correct 253 ms 8512 KB Output is correct
8 Correct 257 ms 8580 KB Output is correct
9 Correct 268 ms 8500 KB Output is correct
10 Correct 275 ms 8568 KB Output is correct
11 Correct 270 ms 8804 KB Output is correct
12 Correct 258 ms 9372 KB Output is correct
13 Correct 285 ms 9264 KB Output is correct
14 Correct 303 ms 9384 KB Output is correct
15 Correct 242 ms 8516 KB Output is correct
16 Correct 232 ms 8496 KB Output is correct
17 Correct 287 ms 9216 KB Output is correct
18 Correct 277 ms 9044 KB Output is correct
19 Correct 229 ms 8528 KB Output is correct
20 Correct 255 ms 9580 KB Output is correct
21 Correct 219 ms 9080 KB Output is correct
22 Correct 230 ms 9104 KB Output is correct
23 Correct 246 ms 8936 KB Output is correct
24 Correct 248 ms 9284 KB Output is correct
25 Correct 275 ms 10792 KB Output is correct

Subtask #5
0 / 18.0

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