Submission #297141

#	Time	Username	Problem	Language	Result	Execution time	Memory
297141		RealSuperman1	Highway Tolls (IOI18_highway)	C++14	100 / 100	387 ms	18664 KiB

highway

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define pii pair<int, int>
 
using namespace std;
 
//const int N = 2e5 + 10;
 
int n, m;
vector < vector <pii> > g, gr;
vector <int> h, visited;
vector <pii> par;
 
void dfs(int u, int p, int id_w, int height) {
	h[u] = height;
	par[u] = {p, id_w};
	for (auto to : gr[u])
		if (to.fi != p)
			dfs(to.fi, u, to.se, h[u] + 1);
}

void dfs_count(int u, int p) {
	visited.pb(u);
	for (auto to : gr[u])
		if (to.fi != p)
			dfs_count(to.fi, u);
}

bool cmp(pii x, pii y) {return x.se > y.se;}
 
int solve_from(int x, int dist, ll val, vector <int> vertical) {
	visited.clear();
	dfs_count(x, -1);
	h.resize(n);
	par.resize(n);
	dfs(x, -1, -1, 0);
	vector <pii> c(visited.size());
	for (int i = 0; i < visited.size(); i++)
		c[i] = {visited[i], h[visited[i]]};
	sort(c.begin(), c.end(), cmp);
	int L = 0, R = visited.size() - 1, M;
	int idc = visited.size() - 1;
	vector <int> w;
	while (L <= R) {
		w.assign(m, 0);
		for (int to : vertical)
			w[to] = 1;
		M = (L + R) / 2;
		for (int i = 0; i <= M; i++)
			if (par[c[i].fi].fi != -1)
				w[par[c[i].fi].se] = 1;
		ll curval = ask(w);
		if (curval > val) {
			idc = min(idc, M);
			R = M - 1;
		} else
			L = M + 1;
	}
	return c[idc].fi;
}

void bfs_tree(int x, int y) {
	queue <int> q;
	q.push(x);
	q.push(y);
	vector <bool> vis(n, false);
	vis[x] = vis[y] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (auto to : g[cur]) {
			if (vis[to.fi])
				continue;
			vis[to.fi] = true;
			q.push(to.fi);
//			cout << cur << " " << to.fi << endl;
			gr[cur].pb(to);
			gr[to.fi].pb({cur, to.se});
		}
	}
}

void find_pair(int n1, vector <int> U, vector <int> V, int A, int B) {
	n = n1;
	m = U.size();
	g.resize(n);
	gr.resize(n);
	for (int i = 0; i < m; i++) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}
	vector <int> w(m, 0);
	ll val = ask(w);
	int dist = (val / (A * 1ll));
	int L = 0, R = m - 1, M, x = m;
	while (L <= R) {
		w.assign(m, 0);
		M = (L + R) / 2;
		for (int i = 0; i <= M; i++)
			w[i] = 1;
		ll curval = ask(w);
		if (curval > val) {
			x = min(x, M);
			R = M - 1;
		} else
			L = M + 1;
	}
//	cout << x << " " << U[x] << " " << V[x] << endl;
//	cout << x << endl;
//	return;
	bfs_tree(U[x], V[x]);
	vector <bool> vis(m, false);
	vector <int> vertical;
	for (int i = 0; i < n; i++)
		for (auto to : gr[i])
			vis[to.se] = true;
	for (int i = 0; i < m; i++)
		if (!vis[i] && i != x)
			vertical.pb(i);
			
	int s = solve_from(U[x], dist, val, vertical); 
	int t = solve_from(V[x], dist, val, vertical);
//	cout << s << " " << t << endl;
	answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'int solve_from(int, int, long long int, std::vector<int>)':
highway.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 0; i < visited.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~

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