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
#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);
	}
}
# 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
# 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
# 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
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 2288 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1184 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -