Submission #301656

#	Time	Username	Problem	Language	Result	Execution time	Memory
301656		dsjong	Highway Tolls (IOI18_highway)	C++14	Compilation error	0 ms	0 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
int A, B, N, M;
long long len;
map<pair<int, int>, int>mp;
vector<int>adj[100005];
bool vis[100005];
int par[100005];
vector<pair<int, int>>bord;
void bfs(int src){
	queue<int>q;
	vis[src]=true;
	q.push(src);
	par[src]=-1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int y:adj[x]){
			if(vis[y]) continue;
			vis[y]=true;
			q.push(y);
			par[y]=x;
			bord.push_back({mp[{x, y}], y});
		}
	}
}
int tin[100005], tout[100005];
int cnt=0;
vector<pair<int, int>>vin, vout;
void dfs(int x, int p){
	tin[x]=cnt++;
	for(int y:adj[x]){
		if(y==p) continue;
		dfs(y, x);
		vin.push_back({tin[y], y});
		vout.push_back({tout[y], y});
	}
	tout[x]=cnt++;
}
vector<int>query, askv;
bool hasB(){
	for(int i=0;i<M;i++) askv[i]=0;
	for(int x:query) askv[x]=1;
	query.clear();
	return ask(askv) > A*len;
}
void find_pair(int _N, std::vector<int> &U, std::vector<int> &V, int _A, int _B) {
	A=_A, B=_B, N=_N, M=U.size();
	askv.resize(M);
	for(int i=0;i<M;i++) askv[i]=0;
	len=ask(askv)/A;
	for(int i=0;i<M;i++){
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
		mp[{U[i], V[i]}]=i;
		mp[{V[i], U[i]}]=i;
	}
	bfs(0);
	int L=0, R=M-1;
	while(L<R){
		int M=(L+R)/2;
		for(int i=0;i<=M;i++){
			query.push_back(bord[i].first);
		}
		if(hasB()) R=M;
		else L=M+1;
	}
	int rt=par[bord[L].second];
	dfs(rt, par[rt]);
	sort(vin.begin(), vin.end());
	sort(vout.begin(), vout.end());
	reverse(vin.begin(), vin.end());
	int pt1, pt2;
	//find largest in
	L=0, R=(int) vin.size()-1;
	while(L<R){
		int M=(L+R)/2;
		for(int i=0;i<=M;i++){
			int cur=vin[i].S;
			query.push_back(mp[{cur, par[cur]}]);
		}
		if(hasB()) R=M;
		else L=M+1;
	}
	pt1=vin[L].S;
	L=0, R=(int) vin.size()-1;
	while(L<R){
		int M=(L+R)/2;
		for(int i=0;i<=M;i++){
			int cur=vout[i].S;
			query.push_back(mp[{cur, par[cur]}]);
		}
		if(hasB()) R=M;
		else L=M+1;
	}
	pt2=vout[L].S;
	if(pt1==pt2) answer(pt1, rt);
	else answer(pt1, pt2);
}

Compilation message (stderr)

/tmp/ccqbwXpl.o: In function `main':
grader.cpp:(.text.startup+0x11c): undefined reference to `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status