oj.uz

Submission #1072070

# Submission time Handle Problem Language Result Execution time Memory
1072070 2024-08-23T13:58:24 Z Joshua_Andersson Highway Tolls (IOI18_highway) C++14
100 / 100
 212 ms 13616 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 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);
		priority_queue<tuple<int,int,int>> q;
		vi vis(n);

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

			nodedist[a] = -d*s;
			repe(e, edges[a])
			{
				if (vis[e.first])
				{
					if (edgedist[e.second]==0)
					{
						edgedist[e.second] = -int(1e7);
					}
				}
				else
				{
					vis[e.first] = 1;
					istree[e.second] = 1;
					edgedist[e.second] = -d * s * (e.first == v ? -1 : 1);
					q.emplace(d - 1, s * (e.first == v ? -1 : 1), e.first);
				}
			}
		}
		nodedist[u] = -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 = n;
		for (int i = m-1; i >= 0; i--) if (edge_order[i].first < 0) hi = i;
		while (lo+1<hi)
		{
			int mid = (lo + hi) / 2;
			vi w(m);
			rep(i, m)
			{
				if (!istree[i]) w[i] = 1;
			}
			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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 13 ms 1784 KB Output is correct
3 Correct 123 ms 10668 KB Output is correct
4 Correct 128 ms 10664 KB Output is correct
5 Correct 136 ms 10536 KB Output is correct
6 Correct 114 ms 10432 KB Output is correct
7 Correct 117 ms 10596 KB Output is correct
8 Correct 110 ms 10496 KB Output is correct
9 Correct 113 ms 10684 KB Output is correct
10 Correct 119 ms 10412 KB Output is correct
11 Correct 111 ms 9832 KB Output is correct
12 Correct 109 ms 9836 KB Output is correct
13 Correct 103 ms 10056 KB Output is correct
14 Correct 104 ms 9920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1368 KB Output is correct
2 Correct 16 ms 2560 KB Output is correct
3 Correct 20 ms 3460 KB Output is correct
4 Correct 75 ms 9748 KB Output is correct
5 Correct 77 ms 9928 KB Output is correct
6 Correct 72 ms 9936 KB Output is correct
7 Correct 80 ms 9924 KB Output is correct
8 Correct 74 ms 9940 KB Output is correct
9 Correct 75 ms 10128 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 13 ms 1544 KB Output is correct
3 Correct 88 ms 8604 KB Output is correct
4 Correct 112 ms 10468 KB Output is correct
5 Correct 113 ms 10640 KB Output is correct
6 Correct 109 ms 10508 KB Output is correct
7 Correct 121 ms 10672 KB Output is correct
8 Correct 113 ms 10640 KB Output is correct
9 Correct 134 ms 10712 KB Output is correct
10 Correct 129 ms 10664 KB Output is correct
11 Correct 112 ms 9916 KB Output is correct
12 Correct 115 ms 9932 KB Output is correct
13 Correct 107 ms 9828 KB Output is correct
14 Correct 117 ms 9956 KB Output is correct
15 Correct 124 ms 10484 KB Output is correct
16 Correct 119 ms 10476 KB Output is correct
17 Correct 104 ms 10056 KB Output is correct
18 Correct 102 ms 9924 KB Output is correct
19 Correct 112 ms 10668 KB Output is correct
20 Correct 97 ms 9920 KB Output is correct
21 Correct 105 ms 12068 KB Output is correct
22 Correct 97 ms 12060 KB Output is correct
23 Correct 132 ms 11408 KB Output is correct
24 Correct 110 ms 11288 KB Output is correct
25 Correct 127 ms 10104 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1624 KB Output is correct
2 Correct 16 ms 1724 KB Output is correct
3 Correct 134 ms 11280 KB Output is correct
4 Correct 166 ms 12008 KB Output is correct
5 Correct 183 ms 13108 KB Output is correct
6 Correct 191 ms 13116 KB Output is correct
7 Correct 178 ms 13128 KB Output is correct
8 Correct 212 ms 13128 KB Output is correct
9 Correct 134 ms 9824 KB Output is correct
10 Correct 120 ms 10152 KB Output is correct
11 Correct 138 ms 11380 KB Output is correct
12 Correct 189 ms 12272 KB Output is correct
13 Correct 190 ms 12716 KB Output is correct
14 Correct 184 ms 13100 KB Output is correct
15 Correct 207 ms 13104 KB Output is correct
16 Correct 157 ms 11148 KB Output is correct
17 Correct 110 ms 12200 KB Output is correct
18 Correct 110 ms 12364 KB Output is correct
19 Correct 108 ms 12328 KB Output is correct
20 Correct 140 ms 12400 KB Output is correct
21 Correct 190 ms 12940 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1624 KB Output is correct
2 Correct 14 ms 1624 KB Output is correct
3 Correct 145 ms 11324 KB Output is correct
4 Correct 151 ms 11576 KB Output is correct
5 Correct 162 ms 11872 KB Output is correct
6 Correct 193 ms 13116 KB Output is correct
7 Correct 125 ms 11300 KB Output is correct
8 Correct 160 ms 11568 KB Output is correct
9 Correct 157 ms 11884 KB Output is correct
10 Correct 180 ms 13100 KB Output is correct
11 Correct 207 ms 13480 KB Output is correct
12 Correct 182 ms 13116 KB Output is correct
13 Correct 140 ms 11164 KB Output is correct
14 Correct 127 ms 10284 KB Output is correct
15 Correct 137 ms 11176 KB Output is correct
16 Correct 114 ms 10288 KB Output is correct
17 Correct 133 ms 11152 KB Output is correct
18 Correct 122 ms 10480 KB Output is correct
19 Correct 188 ms 12276 KB Output is correct
20 Correct 185 ms 12692 KB Output is correct
21 Correct 183 ms 13092 KB Output is correct
22 Correct 187 ms 13092 KB Output is correct
23 Correct 194 ms 13616 KB Output is correct
24 Correct 188 ms 13116 KB Output is correct
25 Correct 183 ms 13104 KB Output is correct
26 Correct 184 ms 13108 KB Output is correct
27 Correct 110 ms 12412 KB Output is correct
28 Correct 115 ms 12180 KB Output is correct
29 Correct 104 ms 12544 KB Output is correct
30 Correct 114 ms 12348 KB Output is correct
31 Correct 108 ms 12316 KB Output is correct
32 Correct 109 ms 12224 KB Output is correct
33 Correct 121 ms 12488 KB Output is correct
34 Correct 110 ms 12300 KB Output is correct
35 Correct 108 ms 12484 KB Output is correct
36 Correct 111 ms 12208 KB Output is correct
37 Correct 110 ms 12420 KB Output is correct
38 Correct 110 ms 12164 KB Output is correct
39 Correct 172 ms 12736 KB Output is correct
40 Correct 180 ms 12924 KB Output is correct
41 Correct 171 ms 12652 KB Output is correct
42 Correct 179 ms 12732 KB Output is correct