Submission #432764

#	Time	Username	Problem	Language	Result	Execution time	Memory
432764		frodakcin	Highway Tolls (IOI18_highway)	C++11	0 / 100	38 ms	24380 KiB

highway

#include "highway.h"
#include <cstdio>
#include <cassert>

const int MN = 9e4+10;
const int MM = 1.3e5+10;

using ll = long long;

struct edg
{
	public:
		int n, i;
};

std::vector<edg> a[MN];
int pre[MN], ctr, pid[MN], ord[MN], d[MN], post[MN];

void dfs(int n, int p=-1)
{
	ord[ctr] = n;
	pre[n]=ctr++;
	for(int i=0;i<(int)a[n].size();++i)
	{
		if(a[n][i].n == p)
		{
			a[n].erase(a[n].begin()+i);
			--i;
			continue;
		}
		d[a[n][i].n]=d[n]+1;
		pid[a[n][i].n]=a[n][i].i;
		dfs(a[n][i].n, n);
	}
	post[n]=ctr;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
	for(int i=0;i<M;++i)
	{
		a[U[i]].push_back({V[i], i});
		a[V[i]].push_back({U[i], i});
	}
	std::vector<int> w(M, 0);
	ll dist_raw = ask(w); // -1
	int dist = (int)(dist_raw/A);

	dfs(0);
	assert(ctr == N);

	int lca=-1;
	{ // -17
		int l=0, r=N;
		for(;r-l>1;)
		{
			int m=l+(r-l)/2;
			w.assign(M, 0);
			for(int i=l;i<m;++i)
				for(auto x:a[ord[i]])
					w[x.i]=1;
			if(ask(w)>dist_raw)
				r = m;
			else
				l = m;
		}
		lca=ord[l];
	}

	int S;
	{ // -17
		int l=pre[lca]+1;
		int r=post[lca];
		for(;r-l>1;)
		{
			int m=l+(r-l)/2;
			w.assign(M, 0);
			for(int i=m;i<r;++i)
				w[pid[ord[i]]]=1;
			//printf("%d %d %d %lld\n", ord[l], ord[m], ord[r], ask(w));
			if(ask(w)>dist_raw)
				l = m;
			else
				r = m;
			//printf("%d %d\n", l, r);
		}
		S = ord[l];
	}

	int T;
	{ // -17
		std::vector<int> cand;
		for(int i=pre[lca];i<pre[S];++i)
			if(d[ord[i]] + d[S] - 2*d[lca] == dist)
				cand.push_back(ord[i]);
		int l=0, r=cand.size(); // can binsearch from left or right now
		for(;r-l>1;)
		{
			int m=l+(r-l)/2;
			w.assign(M, 0);
			for(int i=l;i<m;++i)
				w[pid[cand[i]]]=1;
			if(ask(w) > dist_raw)
				r = m;
			else
				l = m;
		}
		T = cand[l];
	}

	printf("%d %d\n", S, T);
	answer(S, T);
}

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