Submission #130677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130677	2019-07-15T19:53:05 Z	mahmoudbadawy	Highway Tolls (IOI18_highway)	C++17	18 / 100	214 ms	9056 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];
  	}
  	swap(s,t);
  	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	2600 KB	Output is correct
2	Correct	4 ms	2600 KB	Output is correct
3	Correct	4 ms	2680 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2552 KB	Output is correct
6	Correct	4 ms	2552 KB	Output is correct
7	Correct	4 ms	2600 KB	Output is correct
8	Correct	4 ms	2552 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2552 KB	Output is correct
11	Correct	4 ms	2552 KB	Output is correct
12	Correct	5 ms	2552 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2684 KB	Output is correct
2	Correct	18 ms	3388 KB	Output is correct
3	Correct	208 ms	8932 KB	Output is correct
4	Correct	205 ms	8984 KB	Output is correct
5	Correct	208 ms	8992 KB	Output is correct
6	Correct	201 ms	9044 KB	Output is correct
7	Correct	193 ms	9040 KB	Output is correct
8	Correct	214 ms	9056 KB	Output is correct
9	Correct	201 ms	8940 KB	Output is correct
10	Correct	213 ms	9044 KB	Output is correct
11	Correct	206 ms	8444 KB	Output is correct
12	Correct	207 ms	8456 KB	Output is correct
13	Correct	195 ms	8364 KB	Output is correct
14	Correct	193 ms	8368 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	3212 KB	Output is correct
2	Correct	42 ms	3976 KB	Output is correct
3	Correct	58 ms	4572 KB	Output is correct
4	Correct	175 ms	8368 KB	Output is correct
5	Correct	159 ms	8368 KB	Output is correct
6	Correct	155 ms	8312 KB	Output is correct
7	Correct	151 ms	8392 KB	Output is correct
8	Correct	174 ms	8388 KB	Output is correct
9	Correct	148 ms	8460 KB	Output is correct