Submission #1068253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068253		Faisal_Saqib	Highway Tolls (IOI18_highway)	C++17	18 / 100	243 ms	262144 KiB

highway

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
long long ask(const std::vector<int> &w);
void answer(int s, int t);
const ll NP=1e5;
vector<pair<ll,ll>> ma[NP],tmp;
vector<int> w;
ll mi,a,b,par[NP],vis[NP];
ll wantd;
vector<int> ans;
void dfs(int x,int p=-1,ll d=0)
{
	par[x]=p;
	if(d==(wantd))
		ans.pb(x);
	for(auto y:ma[x])
	{
		if(y.second!=p)
		{
			dfs(y.second,x,d+1);
		}
	}
}
map<pair<int,int>,int> edg;
// vector<int> path,node;
// void dfs_(int x,int p=-1)
// {
// 	node.pb(x);
// 	for(auto [id,y]:ma[x])
// 	{
// 		if(y!=p)
// 		{
// 			path.push_back(id);
// 			dfs_(y,x);
// 		}
// 	}
// }
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B)
{
	bool subtask=1;
	int m=u.size();
	w.resize(m,0);
	a=A;
	b=B;
	mi=ask(w);
		// cout<<"For w: ";
		// for(auto j:w)
		// 	cout<<j<<' ';
		// cout<<endl;
		// cout<<"answer "<<mi<<endl;
	wantd=(mi/a);
	for(int i=0;i<n;i++)
		ma[i].clear();
	for(int i=0;i<m;i++)
	{
		edg[{u[i],v[i]}]=i;
		edg[{v[i],u[i]}]=i;
		ma[u[i]].pb({i,v[i]});
		ma[v[i]].pb({i,u[i]});
	}
	for(int i=0;i<m;i++)
	{
		if(u[i]==i and v[i]==(i+1))
		{

		}
		else{
			subtask=0;
		}
	}
	if(subtask)
	{
		int s=-1;
		int e=n;
		while(s+1<e)
		{
			int mid=(s+e)/2;
			for(int j=0;j<=mid;j++)
			{
				w[j]=1;
			}
			ll wa=ask(w);
			// cout<<"Check S "<<mid<<endl;
			// cout<<"For w: ";
			// for(auto j:w)
			// 	cout<<j<<' ';
			// cout<<endl;
			// cout<<"answer "<<wa<<endl;
			for(int j=0;j<=mid;j++)
			{
				w[j]=0;
			}
			if(wa==mi)
			{
				s=mid;
				// no edge 
			}
			else
			{
				e=mid;
			}
		}
		int str=s;
		s=-1;
		e=n;
		while(s+1<e)
		{
			int mid=(s+e)/2;
			for(int j=n-1;j>=mid;j--)
			{
				w[j]=1;
			}
			ll wa=ask(w);
			// cout<<"Check E "<<mid<<endl;
			// cout<<"For w: ";
			// for(auto j:w)
			// 	cout<<j<<' ';
			// cout<<endl;
			// cout<<"answer "<<wa<<endl;
			for(int j=n-1;j>=mid;j--)
			{
				w[j]=0;
			}
			if(wa==mi)
			{
				e=mid;
				// no edge 
			}
			else
			{
				s=mid;
			}
		}
		// cout<<"Check\n";
		// cout<<str+1<<' '<<e<<endl;
		answer(str+1,e);
	}
	else
	{

		dfs(0);
		int s=-1;
		int e=ans.size();
		while(s+1<e)
		{
			int mid=(s+e)/2;
			for(int i=0;i<n;i++)
				vis[i]=0;
			vector<int> cur;
			for(int j=s+1;j<=mid;j++)
			{
				int s=ans[j];
				while(s!=0)
				{
					if(vis[s])break;
					vis[s]=1;
					cur.push_back(edg[{s,par[s]}]);
					s=par[s];
				}
			}
			for(auto i:cur)
				w[i]=1;
			ll wa=ask(w);
			for(auto i:cur)
				w[i]=0;
			if(wa==(b*wantd))
			{
				e=mid;
			}
			else
			{
				s=mid;
			}
		}
		answer(0,ans[e]);
	}
}

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