oj.uz

Submission #136457

# Submission time Handle Problem Language Result Execution time Memory
136457 2019-07-25T10:28:40 Z amiratou Highway Tolls (IOI18_highway) C++14
12 / 100
 177 ms 7816 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<vector<ii> > vec;
vector<int> query;
vector<ii> target;
ll dist,a,b;
void dfs(int node,ll d,int high,int p){
	if(d*a==dist){
		target.pb(ii(high,node));
		return;
	}
	for(auto child:vec[node])
		if(child.fi!=p)
			dfs(child.fi,d+1,child.se,node);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = U.size();
	a=A,b=B;
	vec.resize(N);
	query.resize(M);
	for (int i = 0; i < M; ++i)
	{
		vec[U[i]].pb(ii(V[i],i));
		vec[V[i]].pb(ii(U[i],i));
	}
	fill(query.begin(),query.end(),0);
	dist=ask(query);
	dfs(0,0,-1,0);
	sort(target.begin(),target.end());
	int l=0,r=(int)target.size()-1,ans=0;
	while(l<=r){
		int med=(l+r)>>1;
		fill(query.begin(),query.end(),0);
		for (int i = l; i <= med; ++i)
			query[target[i].fi]=1;
		ll check=ask(query);
		if(check!=dist){
			ans=med;
			r=med-1;
		}
		else l=med+1;
	}
	answer(0, target[ans].se);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 0 ms 248 KB Output is correct
4 Correct 2 ms 308 KB Output is correct
5 Correct 2 ms 292 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 276 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 2 ms 420 KB Output is correct
11 Correct 2 ms 296 KB Output is correct
12 Correct 2 ms 296 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 11 ms 1084 KB Output is correct
3 Correct 147 ms 7800 KB Output is correct
4 Correct 131 ms 7784 KB Output is correct
5 Correct 147 ms 7804 KB Output is correct
6 Correct 128 ms 7640 KB Output is correct
7 Correct 114 ms 7696 KB Output is correct
8 Correct 135 ms 7808 KB Output is correct
9 Correct 134 ms 7632 KB Output is correct
10 Correct 135 ms 7812 KB Output is correct
11 Correct 158 ms 7204 KB Output is correct
12 Correct 170 ms 7720 KB Output is correct
13 Correct 150 ms 7556 KB Output is correct
14 Correct 177 ms 7816 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1028 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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