Submission #360154

#	Time	Username	Problem	Language	Result	Execution time	Memory
360154		arnold518	Highway Tolls (IOI18_highway)	C++14	51 / 100	289 ms	262148 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<pii> adj[MAXN+10];

int TT[MAXM+10];
ll query()
{
	vector<int> V;
	for(int i=0; i<M; i++) V.push_back(TT[i+1]);
	return ask(V);
}

ll query2()
{
	return (query()-D*A)/(B-A);
}

int P[MAXN+10], dep[MAXN+10], L[MAXN+10], R[MAXN+10], cnt;
vector<int> V;

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	L[now]=++cnt;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		V.push_back(nxt.second);
		P[nxt.first]=nxt.second;
		dfs(nxt.first, now, d+1);
		V.push_back(nxt.second);
	}
	R[now]=cnt;
}

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, i});
		adj[E[i].second].push_back({E[i].first, i});
	}
	A=_A; B=_B;

	dfs(1, 1, 0);

	memset(TT, 0, sizeof(TT));
	D=query()/A;

	int LL, RR;

	int lo=-1, hi=V.size()-1;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int j=0; j<=mid; j++) TT[V[j]]=1;

		if(query2()>=D) hi=mid;
		else lo=mid;

		for(int j=0; j<=mid; j++) TT[V[j]]=0;
	}
	RR=hi;

	lo=0, hi=RR+1;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int j=mid; j<=RR; j++) TT[V[j]]=1;

		if(query2()>=D) lo=mid;
		else hi=mid;

		for(int j=mid; j<=RR; j++) TT[V[j]]=0;
	}
	LL=lo;

	if(dep[E[V[RR]].first]>dep[E[V[RR]].second]) swap(E[V[RR]].first, E[V[RR]].second);
	if(dep[E[V[LL]].first]>dep[E[V[LL]].second]) swap(E[V[LL]].first, E[V[LL]].second);

	T=E[V[RR]].second;

	//printf("%d %d\n", LL, RR);
	//printf("%d %d / %d %d\n", E[V[LL]].first, E[V[LL]].second, E[V[RR]].first, E[V[RR]].second);

	if(L[E[V[LL]].second]<=L[T] && R[T]<=R[E[V[LL]].second]) S=E[V[LL]].first;
	else S=E[V[LL]].second;

	//printf("!%d %d\n", S, T);
	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:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:82:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int mid=lo+hi>>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