oj.uz

Submission #422784

# Submission time Handle Problem Language Result Execution time Memory
422784 2021-06-10T12:17:54 Z alireza_kaviani Highway Tolls (IOI18_highway) C++11
51 / 100
 286 ms 15476 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;
int n , timer , st[MAXN] , prv[MAXN];
vector<pii> adj[MAXN];

vector<int> get(int x){
	vector<int> ans(n - 1 , 0);
	for(int i = 0 ; i < n ; i++){
		if(st[i] >= x)	ans[prv[i]] = 1;
	}
	return ans;
}

void DFS(int v , int p = -1){
	st[v] = ++timer;
	for(pii i : adj[v]){
		int u = i.first , w = i.second;
		if(u == p)	continue;
		prv[u] = w;
		DFS(u , v);
	}
}

int solve(int root){
	fill(st , st + MAXN , 0);
	fill(prv , prv + MAXN , -1);
	timer = 0 , DFS(root);
	int l = 0 , r = n;
	long long dist = ask(get(n));
	while(r - l > 1){
		int mid = l + r >> 1;
		if(ask(get(mid)) > dist)	l = mid;
		else	r = mid;
	}
	for(int i = 0 ; i < n ; i++)	if(st[i] == l)	return i;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	if(U.size() != N - 1)	return; n = N;
	for(int i = 0 ; i < n - 1 ; i++){
		adj[V[i]].push_back({U[i] , i});
		adj[U[i]].push_back({V[i] , i});
	}
	int s = solve(0) , t = solve(s);
	answer(s , t);
}

Compilation message

highway.cpp: In function 'int solve(int)':
highway.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l + r >> 1;
      |             ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:44:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  if(U.size() != N - 1) return; n = N;
      |     ~~~~~~~~~^~~~~~~~
highway.cpp:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |  if(U.size() != N - 1) return; n = N;
      |  ^~
highway.cpp:44:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |  if(U.size() != N - 1) return; n = N;
      |                                ^
highway.cpp: In function 'int solve(int)':
highway.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6472 KB Output is correct
2 Correct 5 ms 6472 KB Output is correct
3 Correct 5 ms 6472 KB Output is correct
4 Correct 5 ms 6472 KB Output is correct
5 Correct 5 ms 6472 KB Output is correct
6 Correct 4 ms 6472 KB Output is correct
7 Correct 4 ms 6472 KB Output is correct
8 Correct 4 ms 6472 KB Output is correct
9 Correct 4 ms 6472 KB Output is correct
10 Correct 4 ms 6472 KB Output is correct
11 Correct 5 ms 6472 KB Output is correct
12 Correct 4 ms 6472 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6600 KB Output is correct
2 Correct 23 ms 7116 KB Output is correct
3 Correct 210 ms 11752 KB Output is correct
4 Correct 205 ms 11752 KB Output is correct
5 Correct 198 ms 11688 KB Output is correct
6 Correct 207 ms 11744 KB Output is correct
7 Correct 177 ms 11688 KB Output is correct
8 Correct 139 ms 11692 KB Output is correct
9 Correct 195 ms 11684 KB Output is correct
10 Correct 134 ms 11788 KB Output is correct
11 Correct 215 ms 12156 KB Output is correct
12 Correct 210 ms 12752 KB Output is correct
13 Correct 178 ms 12272 KB Output is correct
14 Correct 222 ms 12340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7496 KB Output is correct
2 Correct 29 ms 8444 KB Output is correct
3 Correct 40 ms 9472 KB Output is correct
4 Correct 127 ms 15364 KB Output is correct
5 Correct 122 ms 15448 KB Output is correct
6 Correct 118 ms 15356 KB Output is correct
7 Correct 118 ms 15360 KB Output is correct
8 Correct 134 ms 15476 KB Output is correct
9 Correct 181 ms 15356 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6600 KB Output is correct
2 Correct 17 ms 7124 KB Output is correct
3 Correct 109 ms 10552 KB Output is correct
4 Correct 150 ms 11680 KB Output is correct
5 Correct 197 ms 11696 KB Output is correct
6 Correct 203 ms 11688 KB Output is correct
7 Correct 187 ms 11696 KB Output is correct
8 Correct 168 ms 11780 KB Output is correct
9 Correct 163 ms 11688 KB Output is correct
10 Correct 249 ms 11772 KB Output is correct
11 Correct 209 ms 11940 KB Output is correct
12 Correct 286 ms 12784 KB Output is correct
13 Correct 171 ms 12388 KB Output is correct
14 Correct 164 ms 12704 KB Output is correct
15 Correct 173 ms 11696 KB Output is correct
16 Correct 173 ms 11700 KB Output is correct
17 Correct 209 ms 12488 KB Output is correct
18 Correct 174 ms 12496 KB Output is correct
19 Correct 150 ms 11692 KB Output is correct
20 Correct 163 ms 13172 KB Output is correct
21 Correct 171 ms 11848 KB Output is correct
22 Correct 176 ms 11848 KB Output is correct
23 Correct 161 ms 11868 KB Output is correct
24 Correct 175 ms 12300 KB Output is correct
25 Correct 152 ms 14980 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 5064 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5076 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -