Submission #835058

#	Time	Username	Problem	Language	Result	Execution time	Memory
835058		arnold518	Highway Tolls (IOI18_highway)	C++17	90 / 100	194 ms	11364 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 9e4;
const int MAXM = 13e4;

int N, M, S, T;
ll A, B, D;
pii E[MAXM+10];
vector<int> adj[MAXN+10];

int vis[MAXN+10];
int P[MAXN+10], PP[MAXN+10];

int TT[MAXM+10];
ll query()
{
	vector<int> V;
	//for(int i=1; i<=M; i++) printf("%d ", TT[i]); printf("\n");
	for(int i=0; i<M; i++) V.push_back(TT[i+1]);
	return ask(V);
}

void find_pair(int _N, vector<int> _U, vector<int> _V, int _A, int _B)
{
	N=_N; M=_U.size();
	for(int i=1; i<=M; i++) E[i]={_U[i-1]+1, _V[i-1]+1};
	for(int i=1; i<=M; i++)
	{
		adj[E[i].first].push_back(E[i].second);
		adj[E[i].second].push_back(E[i].first);
	}
	A=_A; B=_B;

	for(int i=1; i<=M; i++) TT[i]=0;
	D=query()/A;

	int lo=0, hi=M;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++) TT[i]=0;
		for(int i=1; i<=mid; i++) TT[i]=1;
		if(D*A!=query()) hi=mid;
		else lo=mid;
	}

	int cnt=1;
	queue<int> Q;
	Q.push(E[hi].first); vis[E[hi].first]=1;

	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		P[now]=cnt++;
		for(auto nxt : adj[now])
		{
			if(vis[nxt]) continue;
			vis[nxt]=vis[now]+1;
			Q.push(nxt);
		}
	}
	for(int i=1; i<=N; i++) PP[P[i]]=i;

	lo=0, hi=N;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(vis[PP[mid]]-1<(D+1)/2) lo=mid;
		else if(vis[PP[mid]]-1>D) hi=mid;
		else
		{
			for(int i=1; i<=M; i++)
			{
				auto [u, v]=E[i];
				if(P[u]<=mid && P[v]<=mid) TT[i]=0;
				else TT[i]=1;
			}
			if(D*A!=query()) lo=mid;
			else hi=mid;
		}
	}
	T=PP[hi];

	cnt=1;
	for(int i=1; i<=N; i++) vis[i]=0;
	Q.push(T); vis[T]=1;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		P[now]=cnt++;
		for(auto nxt : adj[now])
		{
			if(vis[nxt]) continue;
			vis[nxt]=vis[now]+1;
			Q.push(nxt);
		}
	}
	for(int i=1; i<=N; i++) PP[P[i]]=i;

	lo=0, hi=N;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(vis[PP[mid]]-1<D) lo=mid;
		else if(vis[PP[mid]]-1>D) hi=mid;
		else
		{
			for(int i=1; i<=M; i++)
			{
				auto [u, v]=E[i];
				if(P[u]<=mid && P[v]<=mid) TT[i]=0;
				else TT[i]=1;
			}
			if(D*A!=query()) lo=mid;
			else hi=mid;
		}
	}
	S=PP[hi];

	answer(S-1, T-1);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:109:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |   int mid=lo+hi>>1;
      |           ~~^~~

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