Submission #1071900

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1071900	2024-08-23T12:13:35 Z	Joshua_Andersson	Highway Tolls (IOI18_highway)	C++14	6 / 100	199 ms	262144 KB

highway

#include "highway.h"

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

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

typedef long long ll;

void dfs(int u, int p, int d, vector<vector<p2>>&edges, vi& edgedist, vi& nodedist)
{
	nodedist[u] = d;
	repe(e, edges[u])
	{
		if (e.first == p) continue;
		edgedist[e.second] = d;
		dfs(e.first, u, d + 1, edges, edgedist, nodedist);
	}
}

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B)
{
	int m = sz(U);

	ll baseline = ask(vi(m, 0));

	int lo = -1;
	int hi = m;
	while (lo+1<hi)
	{
		int mid = (lo + hi) / 2;
		vi w(m);
		rep(i, mid + 1) w[i] = 1;
		if (ask(w) > baseline)
		{
			hi = mid;
		}
		else lo = mid;
	}

	int u = U[hi];
	int v = V[hi];
	vector<vector<p2>> edges(n);
	rep(i, m)
	{
		int a = U[i];
		int b = V[i];
		edges[a].emplace_back(b, i);
		edges[b].emplace_back(a, i);
	}
	
	vi ans;
	rep(_, 2)
	{
		vi edgedist(m);
		vi nodedist(n);
		dfs(u, v, 10, edges, edgedist, nodedist);
		if (_==0) edgedist[hi] = int(1e6);
		vector<p2> edge_order;
		rep(i, m) edge_order.emplace_back(edgedist[i], i);
		sort(edge_order.rbegin(), edge_order.rend());

		lo = -1;
		hi = m;
		while (lo+1<hi)
		{
			int mid = (lo + hi) / 2;
			vi w(m);
			rep(i, mid + 1) w[edge_order[i].second] = 1;
			if (ask(w) > baseline)
			{
				hi = mid;
			}
			else lo = mid;
		}
		int e = edge_order[hi].second;
		ans.push_back(nodedist[U[e]]>nodedist[V[e]]?U[e]:V[e]);
		swap(u, v);
	}
	

	answer(ans[0], ans[1]);
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Incorrect	9 ms	1504 KB	Output is incorrect: {s, t} is wrong.
3	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	2056 KB	Output is correct
2	Correct	19 ms	3756 KB	Output is correct
3	Correct	25 ms	5548 KB	Output is correct
4	Correct	71 ms	14436 KB	Output is correct
5	Correct	84 ms	14820 KB	Output is correct
6	Correct	75 ms	15968 KB	Output is correct
7	Correct	74 ms	17136 KB	Output is correct
8	Correct	84 ms	15180 KB	Output is correct
9	Correct	76 ms	15408 KB	Output is correct