Submission #466335

#	Time	Username	Problem	Language	Result	Execution time	Memory
466335		LucaDantas	Highway Tolls (IOI18_highway)	C++17	0 / 100	1346 ms	262148 KiB

highway

#include "highway.h"
#include <vector>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;

#define pb push_back

constexpr int maxn = 90010;

struct Edge { int v, id; };

vector<Edge> g[maxn], tree[maxn][2];
vector<int> ord[2], arv[2];
int pai[maxn]; // so preciso salvar o id

int dist[maxn][2];
Edge P[maxn][2];
long long SZ; int M;

void bfs(int s, int k) {
	queue<int> q;
	dist[s][k] = 0;
	q.push(s);

	while(q.size()) {
		int u = q.front(); q.pop();
		for(Edge E : g[u]) {
			if(dist[E.v][k] == -1) {
				dist[E.v][k] = dist[u][k] + 1;
				P[E.v][k] = {u, E.id};
				q.push(E.v);
			}
		}
	}
}

void dfs(int u, int k, int p = 0) {
	// fprintf(stderr, "EU %d - %d\n", u, k);
	for(Edge E : tree[u][k]) {
		int v = E.v, id = E.id;
		if(p != v) {
			dfs(v, k, u);
			pai[v] = id;
		}
	}
	ord[k].pb(u);
}

int get(int k) {
	int l = 0, r = (int)(ord[k].size()) - 2, ans = ord[k].back();
	
	while(l <= r) {
		int m = (l+r) >> 1;
		
		vector<int> w(M, 1);
		for(int x : arv[!k])
			w[x] = 0;

		for(int i = 1; i <= m; i++)
			w[pai[ord[k][i]]] = 0;

		long long aq = ask(w);

		if(aq > SZ) ans = ord[k][m], r = m-1;
		else l = m+1;

		// fprintf(stderr, "OPA %d %lld %lld | %d\n", m, aq, SZ, ans);
	}

	// fprintf(stderr, "%d == %d\n", k, ans);

	return ans;
}

/* void db(vector<int> a) {
	fprintf(stderr, "DEBUG vector:");
	for(int x : a) fprintf(stderr, " %d", x);
	fprintf(stderr, "\n");
} */

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = (int)(U.size());
	vector<int> w(M);
	SZ = ask(w); // pergunta tudo 0 msm só pra saber a distância

	int edge = 0, l = 0, r = M-1;
	while(l <= r) {
		int m = (l+r) >> 1;
		for(int k = 0; k <= m; k++)
			w[k] = 1;
		long long aq = ask(w);
		if(aq > SZ) edge = m, r = m-1;
		else l = m+1;
		for(int& x : w) x = 0;
	}

	// fprintf(stderr, "BOMDIA %d = %d %d\n", edge, U[edge], V[edge]);

	for(int i = edge; i < M; i++) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}

	memset(dist, -1, sizeof dist);
	bfs(U[edge], 0);
	bfs(V[edge], 1);

	for(int i = 0; i < N; i++) {
		if(dist[i][0] < dist[i][1]) {
			tree[i][0].pb(P[i][0]);
			tree[P[i][0].v][0].pb({i, P[i][0].id});
			arv[0].pb(P[i][0].id);
		} else if(dist[i][1] < dist[i][0]) {
			tree[i][1].pb(P[i][1]);
			tree[P[i][1].v][1].pb({i, P[i][1].id});
			arv[1].pb(P[i][1].id);
		}
	}

	dfs(U[edge], 0);
	dfs(V[edge], 1);

	// db(ord[0]); db(ord[1]);

	answer(get(1), get(0));
}

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