Submission #130676

#	Time	Username	Problem	Language	Result	Execution time	Memory
130676		mahmoudbadawy	Highway Tolls (IOI18_highway)	C++17	18 / 100	225 ms	9052 KiB

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31