Submission #130664

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130664	2019-07-15T19:29:06 Z	mahmoudbadawy	Highway Tolls (IOI18_highway)	C++17	6 / 100	184 ms	8108 KB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

vector<int> v;
int vis[N];
vector<pair<int,int> > adj[N];

int query(int l,int r,int m)
{
	vector<int> vv(m,1);
	for(int i=l;i<=r;i++)
		vv[abs(v[i])-1]=0;
	return ask(vv);
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b) 
{
	int m=U.size();
	for(int i=0;i<m;i++)
	{
		adj[U[i]].push_back({V[i],(i+1)});
		adj[V[i]].push_back({U[i],-(i+1)});
	}
	queue<int> q;
	q.push(0);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(auto i:adj[x])
  		{
  			if(vis[i.first]) continue;
  			v.push_back(i.second);
  			q.push(i.first);
  			vis[i.first]=1;
  		}
  	}
  	int f=query(0,v.size()-1,m);
  	int st=0,en=v.size()-1,ans=0;
  	while(st<=en)
  	{
  		int mid=(st+en)/2;
  		if(query(mid,v.size()-1,m)==f)
  		{
  			ans=mid; st=mid+1;
  		}
  		else
  			en=mid-1;
  	}
  	st=ans+1; en=v.size()-1; int ans2=v.size()-1;
  	while(st<=en)
  	{
  		int mid=(st+en)/2;
  		if(query(ans,mid,m)==f)
  		{
  			en=mid-1; ans2=mid;
  		}
  		else
  			st=mid+1;
  	}
  	//cout << v[ans] << " " <<  v[ans2] << endl;
  	int s=(v[ans]>0?U[v[ans]-1]:V[-v[ans]-1]),t=(v[ans2]>0?V[v[ans2]-1]:U[-v[ans2]-1]);
  	//cout << s << " " << t << endl;
  	answer(s,t);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3192 KB	Output is correct
2	Correct	36 ms	3896 KB	Output is correct
3	Correct	58 ms	4452 KB	Output is correct
4	Correct	159 ms	7992 KB	Output is correct
5	Correct	184 ms	8108 KB	Output is correct
6	Correct	147 ms	8000 KB	Output is correct
7	Correct	165 ms	7980 KB	Output is correct
8	Correct	184 ms	7976 KB	Output is correct
9	Correct	167 ms	8056 KB	Output is correct