Submission #835324

#	Time	Username	Problem	Language	Result	Execution time	Memory
835324		arnold518	Highway Tolls (IOI18_highway)	C++17	51 / 100	216 ms	12004 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 dist1[MAXN+10], dist2[MAXN+10];
int P[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;
	}

	queue<int> Q;
	for(int i=1; i<=N; i++) dist1[i]=-1;
	Q.push(E[hi].first); dist1[E[hi].first]=0;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		for(auto nxt : adj[now])
		{
			if(dist1[nxt]!=-1) continue;
			dist1[nxt]=dist1[now]+1;
			Q.push(nxt);
		}
	}

	for(int i=1; i<=N; i++) dist2[i]=-1;
	Q.push(E[hi].second); dist2[E[hi].second]=0;
	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		for(auto nxt : adj[now])
		{
			if(dist2[nxt]!=-1) continue;
			dist2[nxt]=dist2[now]+1;
			Q.push(nxt);
		}
	}

	vector<pii> V1, V2;
	for(int i=1; i<=N; i++)
	{
		if(dist1[i]<dist2[i]) V1.push_back({dist1[i], i});
		if(dist1[i]>dist2[i]) V2.push_back({dist2[i], i});
	}

	sort(V1.begin(), V1.end());
	sort(V2.begin(), V2.end());

	for(int i=0; i<V1.size(); i++) P[V1[i].second]=i+1;
	for(int i=0; i<V2.size(); i++) P[V2[i].second]=-(i+1);

	//for(int i=1; i<=N; i++) printf("%d ", P[i]); printf("\n");

	lo=0, hi=V1.size();
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++)
		{
			auto [u, v]=E[i];
			if(P[u]==0 || P[v]==0) TT[i]=1;
			else if((P[u]>0)!=(P[v]>0)) TT[i]=1;
			else if(P[u]<0) TT[i]=0;
			else if(P[u]<=mid && P[v]<=mid) TT[i]=0;
			else TT[i]=1;
		}
		if(D*A+B-A!=query()) lo=mid;
		else hi=mid;
	}
	for(int i=1; i<=N; i++) if(P[i]==hi) S=i;
	//printf("!%d\n", hi);

	lo=0, hi=V2.size();
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		for(int i=1; i<=M; i++)
		{
			auto [u, v]=E[i];
			if(P[u]==0 || P[v]==0) TT[i]=1;
			else if((P[u]>0)!=(P[v]>0)) TT[i]=1;
			else if(P[u]>0) TT[i]=0;
			else if(-P[u]<=mid && -P[v]<=mid) TT[i]=0;
			else TT[i]=1;
		}
		if(D*A+B-A!=query()) lo=mid;
		else hi=mid;
	}
	for(int i=1; i<=N; i++) if(-P[i]==hi) T=i;
	//printf("!%d\n", 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:90:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=0; i<V1.size(); i++) P[V1[i].second]=i+1;
      |               ~^~~~~~~~~~
highway.cpp:91:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=0; i<V2.size(); i++) P[V2[i].second]=-(i+1);
      |               ~^~~~~~~~~~
highway.cpp:98:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |   int mid=lo+hi>>1;
      |           ~~^~~
highway.cpp:117:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |   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