oj.uz

Submission #297388

# Submission time Handle Problem Language Result Execution time Memory
297388 2020-09-11T14:25:53 Z eohomegrownapps Highway Tolls (IOI18_highway) C++14
51 / 100
 316 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// ll ask(vector<int> w)
// void answer(int a, int b)

vector<vector<pair<int,int>>> adjlist; // node, ind

int n,a,b,m;

vector<int> parentedge;
vector<int> parentnode;

vector<int> preorder;

void dfs(int node, int par){
	preorder.push_back(node);
	for (auto p : adjlist[node]){
		int i = p.first;
		int ni = p.second;
		if (i==par){continue;}
		parentnode[i]=node;
		parentedge[i]=ni;
		dfs(i,node);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n=N;a=A;b=B;m=U.size();
	adjlist.resize(n);
	parentnode.resize(n,-1);
	parentedge.resize(n,-1);
	for (int i = 0; i<U.size(); i++){
		adjlist[U[i]].push_back({V[i],i});
		adjlist[V[i]].push_back({U[i],i});
	}
	dfs(0,-1);

	// what's the total length of the path?
	vector<int> query(m);
	ll len = ask(query)/a;

	// binary search until path is len*b
	int l = 0, r = n-1;
	while (l<=r){
		int mid = (l+r)/2;
		query.assign(m,0);
		for (int i = 1; i<=mid; i++){
			query[parentedge[preorder[i]]]=1;
		}
		ll ans = ask(query);
		if (ans<len*b){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	int root = preorder[l];
	// root at l, then search again
	preorder.clear();
	parentnode[root]=-1;
	parentedge[root]=-1;
	dfs(root,-1);
	l = 0, r = n-1;
	while (l<=r){
		int mid = (l+r)/2;
		query.assign(m,0);
		for (int i = 1; i<=mid; i++){
			query[parentedge[preorder[i]]]=1;
		}
		ll ans = ask(query);
		if (ans<len*b){
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	//cout<<root<<' '<<preorder[l]<<'\n';
	answer(root,preorder[l]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i<U.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 14 ms 1280 KB Output is correct
3 Correct 190 ms 8896 KB Output is correct
4 Correct 191 ms 8992 KB Output is correct
5 Correct 166 ms 8892 KB Output is correct
6 Correct 187 ms 8824 KB Output is correct
7 Correct 192 ms 8824 KB Output is correct
8 Correct 160 ms 8828 KB Output is correct
9 Correct 190 ms 8928 KB Output is correct
10 Correct 182 ms 8916 KB Output is correct
11 Correct 197 ms 10224 KB Output is correct
12 Correct 180 ms 10964 KB Output is correct
13 Correct 176 ms 10204 KB Output is correct
14 Correct 186 ms 10276 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2048 KB Output is correct
2 Correct 25 ms 3832 KB Output is correct
3 Correct 36 ms 5360 KB Output is correct
4 Correct 128 ms 15308 KB Output is correct
5 Correct 121 ms 15336 KB Output is correct
6 Correct 129 ms 15324 KB Output is correct
7 Correct 125 ms 15308 KB Output is correct
8 Correct 129 ms 15400 KB Output is correct
9 Correct 128 ms 15300 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 14 ms 1280 KB Output is correct
3 Correct 137 ms 7000 KB Output is correct
4 Correct 171 ms 8820 KB Output is correct
5 Correct 174 ms 8896 KB Output is correct
6 Correct 188 ms 8824 KB Output is correct
7 Correct 168 ms 8820 KB Output is correct
8 Correct 186 ms 8880 KB Output is correct
9 Correct 193 ms 8820 KB Output is correct
10 Correct 169 ms 8952 KB Output is correct
11 Correct 198 ms 9512 KB Output is correct
12 Correct 194 ms 10952 KB Output is correct
13 Correct 192 ms 10308 KB Output is correct
14 Correct 190 ms 10788 KB Output is correct
15 Correct 166 ms 8840 KB Output is correct
16 Correct 145 ms 8840 KB Output is correct
17 Correct 191 ms 10472 KB Output is correct
18 Correct 193 ms 10540 KB Output is correct
19 Correct 180 ms 8836 KB Output is correct
20 Correct 188 ms 11500 KB Output is correct
21 Correct 140 ms 9008 KB Output is correct
22 Correct 153 ms 9008 KB Output is correct
23 Correct 156 ms 9040 KB Output is correct
24 Correct 197 ms 9932 KB Output is correct
25 Correct 182 ms 14656 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 316 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -