Submission #136486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136486	2019-07-25T11:09:22 Z	amiratou	Highway Tolls (IOI18_highway)	C++14	18 / 100	202 ms	13508 KB

highway

#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,int high,int p){
	if(high!=-1)target.pb(ii(high,node));
	for(auto child:vec[node])
		if(child.fi!=p)
			dfs(child.fi,child.se,node);
}
void dfs2(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)
			dfs2(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);
	bool subtask=1;
	for (int i = 0; i < M; ++i)
	{
		vec[U[i]].pb(ii(V[i],i));
		vec[V[i]].pb(ii(U[i],i));
		if(U[i]!=i||V[i]!=i+1)subtask=0;
	}
	if(subtask){
		int start=0;
		for (int i = 0; i < N; ++i)
		{
			if(vec[i].size()==1){
				start=i;
				break;
			}
		}
		fill(query.begin(),query.end(),0);
		dist=ask(query);
		dfs(start,-1,0);
		//sort(target.begin(),target.end());
		int l=0,r=(int)(target.size())-1;
		int n1=-1,n2=-1,L=0;
		while(l<r){
			int med=(l+r)>>1;
			L=med;
			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)
				l=med+1;
			else if(check==(dist/A)*B){
				r=med;
			}
			else{
				ll nb_edges=(check-dist)/(B-A);
				//cerr<<l<<" "<<r<<" "<<nb_edges<<" "<<med<<"\n";
				n1=(((med-nb_edges)<0)?start:target[med-nb_edges].se);
				n2=target[med+(dist-nb_edges*A)/A].se;
				//cerr<<n1<<" "<<n2<<"\n";
				break;
			}
		}
		if(n1!=-1)
			answer(n1, n2);
		else
			answer((L?target[L-1].se:start),target[L].se);
	}
	else{
		fill(query.begin(),query.end(),0);
		dist=ask(query);
		dfs2(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	308 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	2 ms	248 KB	Output is correct
6	Correct	2 ms	248 KB	Output is correct
7	Correct	2 ms	248 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	248 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	248 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	40 ms	1136 KB	Output is correct
3	Correct	170 ms	7792 KB	Output is correct
4	Correct	179 ms	7784 KB	Output is correct
5	Correct	177 ms	7804 KB	Output is correct
6	Correct	164 ms	7676 KB	Output is correct
7	Correct	137 ms	7796 KB	Output is correct
8	Correct	202 ms	7808 KB	Output is correct
9	Correct	165 ms	7712 KB	Output is correct
10	Correct	179 ms	7732 KB	Output is correct
11	Correct	176 ms	7296 KB	Output is correct
12	Correct	163 ms	7668 KB	Output is correct
13	Correct	199 ms	7588 KB	Output is correct
14	Correct	180 ms	7824 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	1912 KB	Output is correct
2	Correct	31 ms	3280 KB	Output is correct
3	Correct	42 ms	4764 KB	Output is correct
4	Correct	132 ms	13428 KB	Output is correct
5	Correct	146 ms	13508 KB	Output is correct
6	Correct	141 ms	13432 KB	Output is correct
7	Correct	146 ms	13432 KB	Output is correct
8	Correct	161 ms	13408 KB	Output is correct
9	Correct	148 ms	13492 KB	Output is correct