Submission #298234

#	Time	Username	Problem	Language	Result	Execution time	Memory
298234		rqi	Highway Tolls (IOI18_highway)	C++14	51 / 100	313 ms	30072 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){
	queue<int> q;
	dist[node][typ] = 0;
	q.push(node);
	while(sz(q)){
		int a = q.front();
		q.pop();
		for(auto u: adj[a]){
			if(dist[u][typ] > dist[a][typ]+1){
				dist[u][typ] = dist[a][typ];
				q.push(u);
			}
		}
	}
}

vi curw;

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

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

void genTDist(int node){
	queue<int> q;
	tdist[node] = 0;
	q.push(node);
	while(sz(q)){
		int a = q.front();
		q.pop();
		for(auto u: tadj[a]){
			if(tdist[u.f] > tdist[a]+1){
				tdist[u.f] = tdist[a]+1;
				q.push(u.f);
			}
		}
	}
}

void genPO(int node){
	for(auto u: children[node]){
		genPO(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 << "nodes: ";
	// for(auto u: nodes) cout << u << " ";
	// cout << "\n";
	//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);
	
	//for(auto u: nodes) cout << u << " " << tdist[u] << "\n";
	vi tw = curw;
	for(auto u: nodes){
		if(u == R) continue;
		bool found = 0;
		for(auto x: tadj[u]){
			if(tdist[x.f]+1 != tdist[u]) continue;
			if(!found){
				found = 1;
				children[x.f].pb(u);
				par[u] = x;
				//cout << "ED: " << x.f << " " << x.s << " " << u << "\n";
			}
			else{
				//cout << x.s << "\n";
				tw[x.s] = 1;
			}
		}
	}
	genPO(R);
	// cout << "ord: ";
	// for(auto u: ord) cout << u << " ";
	// cout << "\n";
	
	// cout << "tw: ";
	// for(auto u: tw) cout << u << " ";
	// cout << "\n";

	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]);
	}

	//cout << lo << "\n";

	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]);
	//cout << a << " " << b << "\n";
	answer(a, b);
}

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