Submission #122351

#	Time	Username	Problem	Language	Result	Execution time	Memory
122351		tmwilliamlin168	Highway Tolls (IOI18_highway)	C++14	51 / 100	328 ms	14088 KiB

highway

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

const int mxN=9e4;
int m, d1[mxN], d2[mxN];
vector<int> eu, ev, adj[mxN], bv;
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>> p) {
	vector<array<int, 2>> q;
	for(array<int, 2> a : p)
		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=bv;
		for(int i=mb; i<q.size(); ++i)
			w[q[i][1]]=1;
		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);
	}
	bv=vector<int>(m);
	bc=ask(bv);
	int lb=0, rb=m-1;
	while(lb<rb) {
		int mb=(lb+rb)/2;
		vector<int> w=bv;
		fill(w.begin(), w.begin()+mb+1, 1);
		if(ask(w)>bc)
			rb=mb;
		else
			lb=mb+1;
	}
	//cout << lb << endl;
	fill(bv.begin(), bv.begin()+lb, 1);
	bfs(u[lb], d1, p1);
	bfs(v[lb], d2, p2);
	answer(solve(d1, d2, p1), solve(d2, d1, p2));
}

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) {
                ~~^~~~~~~~~
highway.cpp: In function 'int solve(int*, int*, std::vector<std::array<int, 2> >)':
highway.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mb; i<q.size(); ++i)
                 ~^~~~~~~~~

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