Submission #298225

#	Time	Username	Problem	Language	Result	Execution time	Memory
298225		rqi	Highway Tolls (IOI18_highway)	C++14	0 / 100	380 ms	9016 KiB

highway

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

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define ins insert

const int MOD = 1000000007;
const int mx = 90005;
int N, M;
ll A, B;
int D;
ll reg;
vi U, V;
vi adj[mx]; //node, edge
int dist[mx][2];
void genDist(int node, int typ, int d = 0){
	if(dist[node][typ] <= d) return;
	dist[node][typ] = d;
	for(auto u: adj[node]){
		genDist(u, typ, d+1);
	}
}

vi curw;

vpi tadj[mx];
vi ord; //nodes, ordered by postorder
int tdist[mx];

vi children[mx];
pi par[mx];

void genTDist(int node, int prv = -1, int d = 0){
	if(tdist[node] <= d) return;
	tdist[node] = d;
	for(auto u: tadj[node]){
		genTDist(u.f, node, d+1);
	}
}

void genPO(int node){
	for(auto u: children[node]){
		ord.pb(u);
	}
	ord.pb(node);
}

int treeAns(vector<pair<pi, int>> eds, int R){
	set<int> trash;
	for(auto u: eds){
		trash.ins(u.f.f); trash.ins(u.f.s);
	}
	trash.ins(R);

	vi nodes;
	for(auto u: trash) nodes.pb(u);

	//cout << sz(nodes) << "\n";

	ord.clear();
	for(auto u: nodes){
		tadj[u].clear();
		children[u].clear();
		par[u] = mp(-1, -1);
	}
	for(auto u: eds){
		tadj[u.f.f].pb(mp(u.f.s, u.s));
		tadj[u.f.s].pb(mp(u.f.f, u.s));
	}
	for(auto u: nodes) tdist[u] = MOD;
	genTDist(R);
	
	vi tw = curw;
	for(auto u: nodes){
		if(u == R) continue;
		bool found = 0;
		for(auto x: tadj[u]){
			if(!found && tdist[x.f]+1 == tdist[u]){
				found = 1;
				children[x.f].pb(u);
				par[u] = x;
			}
			else{
				tw[x.s] = 1;
			}
		}
	}

	genPO(R);
	int lo = 0;
	int hi = sz(ord)-1;
	while(lo < hi){
		int mid = (lo+hi)/2;
		vi w = tw;
		for(int i = 0; i <= mid; i++){
			w[par[ord[i]].s] = 1;
		}
		if(ask(w) != reg){
			hi = mid;
		}
		else{
			lo = mid+1;
		}
	}

	return ord[lo];
}

void find_pair(int _N, vi _U, vi _V, int _A, int _B) {
	N = _N;
	U = _U;
	V = _V;
	M = sz(U);
	A = _A;
	B = _B;

	reg = ask(vi(M, 0));

	//perhaps random shuffle?
	int lo = 1;
	int hi = M;
	while(lo < hi){
		int mid = (lo+hi)/2;
		vi w(M, 0);
		for(int i = 0; i < mid; i++) w[i] = 1;
		ll res = ask(w);
		if(res == reg){
			lo = mid+1;
		}
		else hi = mid;
	}

	for(int i = lo; i < M; i++){
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
	}

	for(int j = 0; j < 2; j++){
		for(int i = 0; i < N; i++){
			dist[i][j] = MOD;
		}
	}
	genDist(U[lo-1], 0);
	genDist(V[lo-1], 1);

	vector<pair<pi, int>> tr[2];

	for(int i = lo; i < M; i++){
		int typ1 = -1;
		int typ2 = -1;
		int typ;
		if(dist[U[i]][0] < dist[U[i]][1]){
			typ1 = 0;
		}
		else if(dist[U[i]][0] > dist[U[i]][1]){
			typ1 = 1;
		}
		if(dist[V[i]][0] < dist[V[i]][1]){
			typ2 = 0;
		}
		else if(dist[V[i]][0] > dist[V[i]][1]){
			typ2 = 1;
		}

		if(typ1 != typ2) continue;

		typ = typ1;
		if(typ == -1) continue;

		tr[typ].pb(mp(mp(U[i], V[i]), i));
	}

	curw = vi(M, 0);
	for(int i = 0; i < lo-1; i++){
		curw[i] = 1;
	}

	int a = treeAns(tr[0], U[lo-1]);
	int b = treeAns(tr[1], V[lo-1]);
	answer(a, b);
}

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