Submission #1068253

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068253	2024-08-21T08:51:41 Z	Faisal_Saqib	Highway Tolls (IOI18_highway)	C++17	18 / 100	243 ms	262144 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4184 KB	Output is correct
2	Correct	1 ms	2648 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	1 ms	2648 KB	Output is correct
5	Correct	1 ms	2648 KB	Output is correct
6	Correct	1 ms	2648 KB	Output is correct
7	Correct	1 ms	2656 KB	Output is correct
8	Correct	1 ms	2648 KB	Output is correct
9	Correct	1 ms	2648 KB	Output is correct
10	Correct	1 ms	2648 KB	Output is correct
11	Correct	1 ms	2648 KB	Output is correct
12	Correct	1 ms	2648 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2904 KB	Output is correct
2	Correct	14 ms	4832 KB	Output is correct
3	Correct	208 ms	22008 KB	Output is correct
4	Correct	181 ms	21908 KB	Output is correct
5	Correct	179 ms	22060 KB	Output is correct
6	Correct	182 ms	22072 KB	Output is correct
7	Correct	164 ms	22080 KB	Output is correct
8	Correct	186 ms	22176 KB	Output is correct
9	Correct	151 ms	22028 KB	Output is correct
10	Correct	172 ms	22020 KB	Output is correct
11	Correct	156 ms	23452 KB	Output is correct
12	Correct	150 ms	23888 KB	Output is correct
13	Correct	158 ms	23644 KB	Output is correct
14	Correct	181 ms	23116 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	6048 KB	Output is correct
2	Correct	20 ms	6488 KB	Output is correct
3	Correct	31 ms	8396 KB	Output is correct
4	Correct	97 ms	21596 KB	Output is correct
5	Correct	86 ms	21440 KB	Output is correct
6	Correct	92 ms	20040 KB	Output is correct
7	Correct	97 ms	21436 KB	Output is correct
8	Correct	95 ms	21436 KB	Output is correct
9	Correct	100 ms	21432 KB	Output is correct