Submission #130676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130676	2019-07-15T19:50:45 Z	mahmoudbadawy	Highway Tolls (IOI18_highway)	C++17	18 / 100	225 ms	9052 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 par[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);
  			par[i.first]=x;
  			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?V[abs(v[ans])-1]:U[abs(v[ans])-1]),t=(v[ans2]>0?V[abs(v[ans2])-1]:U[abs(v[ans2])-1]);
  	//cout << s << " " << t << endl;
  	int tt=t;
  	while(par[tt])
  	{
  		if(par[tt]==s) {s=par[s]; break;}
  		tt=par[tt];
  	}
  	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	2552 KB	Output is correct
6	Correct	4 ms	2680 KB	Output is correct
7	Correct	4 ms	2680 KB	Output is correct
8	Correct	4 ms	2552 KB	Output is correct
9	Correct	4 ms	2552 KB	Output is correct
10	Correct	4 ms	2600 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2680 KB	Output is correct
2	Correct	25 ms	3392 KB	Output is correct
3	Correct	201 ms	9052 KB	Output is correct
4	Correct	196 ms	9044 KB	Output is correct
5	Correct	192 ms	8924 KB	Output is correct
6	Correct	198 ms	9032 KB	Output is correct
7	Correct	182 ms	9032 KB	Output is correct
8	Correct	210 ms	9040 KB	Output is correct
9	Correct	193 ms	8944 KB	Output is correct
10	Correct	207 ms	8936 KB	Output is correct
11	Correct	189 ms	8384 KB	Output is correct
12	Correct	206 ms	8364 KB	Output is correct
13	Correct	218 ms	8368 KB	Output is correct
14	Correct	225 ms	8416 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3288 KB	Output is correct
2	Correct	42 ms	4108 KB	Output is correct
3	Correct	56 ms	4580 KB	Output is correct
4	Correct	168 ms	8364 KB	Output is correct
5	Correct	142 ms	8364 KB	Output is correct
6	Correct	132 ms	8376 KB	Output is correct
7	Correct	186 ms	8364 KB	Output is correct
8	Correct	160 ms	8360 KB	Output is correct
9	Correct	156 ms	8368 KB	Output is correct