Submission #122358

#	Time	Username	Problem	Language	Result	Execution time	Memory
122358		tmwilliamlin168	Highway Tolls (IOI18_highway)	C++14	100 / 100	379 ms	14996 KiB

highway

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

const int mxN=9e4;
int m, d1[mxN], d2[mxN], me;
vector<int> eu, ev, adj[mxN];
vector<array<int, 2>> p1, p2;
long long bc;

void bfs(int s, int d[mxN], vector<array<int, 2>> &p) {
	memset(d, 0x3f, 4*mxN);
	d[s]=0;
	p.push_back({s});
	for(int qh=0; qh<p.size(); ++qh) {
		int u=p[qh][0];
		for(int e : adj[u]) {
			int v=eu[e]^ev[e]^u;
			if(d[v]>d[u]+1) {
				d[v]=d[u]+1;
				p.push_back({v, e});
			}
		}
	}
}

int solve(int d1[mxN], int d2[mxN], vector<array<int, 2>> p1, vector<array<int, 2>> p2) {
	vector<array<int, 2>> q;
	for(array<int, 2> a : p1)
		if(d1[a[0]]<d2[a[0]])
			q.push_back(a);//, cout << a[0] << " " << a[1] << endl;
	int lb=0, rb=q.size()-1;
	while(lb<rb) {
		int mb=(lb+rb+1)/2;
		vector<int> w(m, 1);
		w[me]=0;
		for(int i=0; i<mb; ++i)
			w[q[i][1]]=0;
		for(array<int, 2> a : p2)
			if(d2[a[0]]<d1[a[0]])
				w[a[1]]=0;
		if(ask(w)>bc)
			lb=mb;
		else
			rb=mb-1;
	}
	return q[lb][0];
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
	eu=u;
	ev=v;
	m=u.size();
	for(int i=0; i<m; ++i) {
		adj[u[i]].push_back(i);
		adj[v[i]].push_back(i);
	}
	bc=ask(vector<int>(m));
	int lb=0, rb=m-1;
	while(lb<rb) {
		int mb=(lb+rb)/2;
		vector<int> w(m);
		fill(w.begin(), w.begin()+mb+1, 1);
		if(ask(w)>bc)
			rb=mb;
		else
			lb=mb+1;
	}
	me=lb;
	//cout << lb << endl;
	bfs(u[me], d1, p1);
	bfs(v[me], d2, p2);
	answer(solve(d1, d2, p1, p2), solve(d2, d1, p2, p1));
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, int*, std::vector<std::array<int, 2> >&)':
highway.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int qh=0; qh<p.size(); ++qh) {
                ~~^~~~~~~~~

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