Submission #130666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130666	2019-07-15T19:35:28 Z	mahmoudbadawy	Highway Tolls (IOI18_highway)	C++17	18 / 100	232 ms	8692 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];

long long 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); vis[0]=1;
	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;
  		}
  	}
  	long long f=query(0,v.size()-1,m);
  	/*for(int i=0;i<v.size();i++)
  		cout << v[i] << " ";
  	cout << endl;*/
  	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[abs(v[ans])-1]:V[abs(v[ans])-1]),t=(v[ans2]>0?V[abs(v[ans2])-1]:U[abs(v[ans2])-1]);
  	//cout << s << " " << t << endl;
  	answer(s,t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	22 ms	3320 KB	Output is correct
3	Correct	191 ms	8664 KB	Output is correct
4	Correct	232 ms	8660 KB	Output is correct
5	Correct	197 ms	8664 KB	Output is correct
6	Correct	215 ms	8656 KB	Output is correct
7	Correct	208 ms	8672 KB	Output is correct
8	Correct	201 ms	8692 KB	Output is correct
9	Correct	199 ms	8640 KB	Output is correct
10	Correct	187 ms	8688 KB	Output is correct
11	Correct	191 ms	8028 KB	Output is correct
12	Correct	199 ms	8024 KB	Output is correct
13	Correct	190 ms	8092 KB	Output is correct
14	Correct	201 ms	8060 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	3336 KB	Output is correct
2	Correct	40 ms	3884 KB	Output is correct
3	Correct	54 ms	4472 KB	Output is correct
4	Correct	175 ms	7980 KB	Output is correct
5	Correct	188 ms	8004 KB	Output is correct
6	Correct	177 ms	8056 KB	Output is correct
7	Correct	157 ms	7984 KB	Output is correct
8	Correct	169 ms	7988 KB	Output is correct
9	Correct	160 ms	8004 KB	Output is correct