oj.uz

Submission #1071986

# Submission time Handle Problem Language Result Execution time Memory
1071986 2024-08-23T13:02:16 Z Joshua_Andersson Highway Tolls (IOI18_highway) C++14
6 / 100
 161 ms 12768 KB 
#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 v, int d, int sign, vector<vector<p2>>&edges, vi& edgedist, vi& nodedist)
{
	nodedist[u] = d;
	repe(e, edges[u])
	{
		if (e.first == p) continue;
		edgedist[e.second] = d*sign * (e.first == v ? -1 : 1);
		dfs(e.first, u, v, d + 1, sign * (e.first==v?-1: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 istree(m);
		vi edgedist(m);
		vi nodedist(n);
		queue<tuple<int,int,int>> q;
		vi vis(n);

		q.emplace(u, 1, 1);
		while (sz(q))
		{
			int a, d, s;
			tie(a, d, s) = q.front();
			q.pop();

			nodedist[a] = d;
			repe(e, edges[a])
			{
				if (vis[e.first])
				{
					//
				}
				else
				{
					vis[e.first] = 1;
					istree[e.second] = 1;
					edgedist[e.second] = d * s * (e.first == v ? -1 : 1);
					q.emplace(e.first, d + 1, s * (e.first == v ? -1 : 1));
				}
			}
		}

		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 Incorrect 1 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1368 KB Output is correct
2 Correct 16 ms 2568 KB Output is correct
3 Correct 30 ms 3440 KB Output is correct
4 Correct 71 ms 10164 KB Output is correct
5 Correct 75 ms 9916 KB Output is correct
6 Correct 69 ms 9812 KB Output is correct
7 Correct 71 ms 9928 KB Output is correct
8 Correct 72 ms 10008 KB Output is correct
9 Correct 69 ms 10064 KB Output is correct

Subtask #4
0 / 33.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 #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1648 KB Output is correct
2 Correct 12 ms 1696 KB Output is correct
3 Correct 117 ms 11124 KB Output is correct
4 Incorrect 150 ms 11648 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1624 KB Output is correct
2 Correct 12 ms 1928 KB Output is correct
3 Correct 130 ms 11660 KB Output is correct
4 Partially correct 121 ms 11348 KB Output is partially correct
5 Partially correct 131 ms 11892 KB Output is partially correct
6 Incorrect 161 ms 12768 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -