제출 #1068212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068212		Faisal_Saqib	Highway Tolls (IOI18_highway)	C++17	12 / 100	221 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;
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B)
{
	int m=u.size();
	w.resize(m,0);
	a=A;
	b=B;
	mi=ask(w);
	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]});
	}
	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: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31