Submission #130688

#	Time	Username	Problem	Language	Result	Execution time	Memory
130688		mahmoudbadawy	Highway Tolls (IOI18_highway)	C++17	51 / 100	320 ms	10872 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)});
	}
	vector<int> anss;
	int root=0;
	for(int x=0;x<2;x++)
	{
		queue<int> q; v.clear();
		memset(vis,0,sizeof vis);
		q.push(root); vis[root]=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;
	  		}
	  	}
	  	reverse(v.begin(), v.end());
	  	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;
	  	}
	  	int s=v[ans]>0?V[v[ans]-1]:U[-v[ans]-1];
	  	root=s; anss.push_back(s);
	}
	//cout << anss[0] << " " << anss[1] << endl;
  	answer(anss[0],anss[1]);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31