oj.uz

Submission #1072067

# Submission time Handle Problem Language Result Execution time Memory
1072067 2024-08-23T13:52:50 Z Joshua_Andersson Highway Tolls (IOI18_highway) C++14
90 / 100
 224 ms 13340 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);
		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;
		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;
		}
		rep(i, m)
		{
			if (_==1)
			{
				int e = edge_order[i].second;
				int k = nodedist[U[e]] > nodedist[V[e]] ? U[e] : V[e];
				if (k== 42568||U[e]== 42568||V[e]== 42568)
				{
					cout << "";
				}
			}
		}
		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 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 600 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 0 ms 344 KB Output is correct
11 Correct 0 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 2 ms 344 KB Output is correct
2 Correct 13 ms 1536 KB Output is correct
3 Correct 124 ms 10660 KB Output is correct
4 Correct 140 ms 10740 KB Output is correct
5 Correct 123 ms 10592 KB Output is correct
6 Correct 119 ms 10636 KB Output is correct
7 Correct 126 ms 10668 KB Output is correct
8 Correct 118 ms 10672 KB Output is correct
9 Correct 114 ms 10676 KB Output is correct
10 Correct 130 ms 10664 KB Output is correct
11 Correct 113 ms 9920 KB Output is correct
12 Correct 110 ms 9924 KB Output is correct
13 Correct 107 ms 10000 KB Output is correct
14 Correct 108 ms 9916 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1368 KB Output is correct
2 Correct 15 ms 2560 KB Output is correct
3 Correct 24 ms 3432 KB Output is correct
4 Correct 78 ms 9920 KB Output is correct
5 Correct 69 ms 9920 KB Output is correct
6 Correct 74 ms 9904 KB Output is correct
7 Correct 80 ms 10068 KB Output is correct
8 Correct 74 ms 9816 KB Output is correct
9 Correct 75 ms 9920 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 12 ms 1616 KB Output is correct
3 Correct 82 ms 8592 KB Output is correct
4 Correct 132 ms 10580 KB Output is correct
5 Correct 116 ms 10876 KB Output is correct
6 Correct 115 ms 10656 KB Output is correct
7 Correct 115 ms 10788 KB Output is correct
8 Correct 130 ms 10636 KB Output is correct
9 Correct 151 ms 10664 KB Output is correct
10 Correct 124 ms 10660 KB Output is correct
11 Correct 118 ms 9928 KB Output is correct
12 Correct 104 ms 9916 KB Output is correct
13 Correct 110 ms 9920 KB Output is correct
14 Correct 116 ms 9920 KB Output is correct
15 Correct 136 ms 10668 KB Output is correct
16 Correct 138 ms 10676 KB Output is correct
17 Correct 117 ms 10044 KB Output is correct
18 Correct 106 ms 9912 KB Output is correct
19 Correct 118 ms 10660 KB Output is correct
20 Correct 124 ms 9968 KB Output is correct
21 Correct 141 ms 12240 KB Output is correct
22 Correct 110 ms 12200 KB Output is correct
23 Correct 119 ms 11420 KB Output is correct
24 Correct 124 ms 11276 KB Output is correct
25 Correct 106 ms 10108 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1652 KB Output is correct
2 Correct 17 ms 1624 KB Output is correct
3 Correct 224 ms 11284 KB Output is correct
4 Correct 191 ms 11972 KB Output is correct
5 Correct 195 ms 13116 KB Output is correct
6 Correct 198 ms 13120 KB Output is correct
7 Correct 197 ms 13132 KB Output is correct
8 Correct 195 ms 13340 KB Output is correct
9 Correct 145 ms 9920 KB Output is correct
10 Correct 126 ms 10360 KB Output is correct
11 Correct 149 ms 11388 KB Output is correct
12 Correct 182 ms 12288 KB Output is correct
13 Correct 205 ms 12720 KB Output is correct
14 Correct 188 ms 13112 KB Output is correct
15 Correct 191 ms 13108 KB Output is correct
16 Correct 147 ms 11152 KB Output is correct
17 Correct 98 ms 12204 KB Output is correct
18 Correct 108 ms 12440 KB Output is correct
19 Correct 126 ms 12396 KB Output is correct
20 Correct 111 ms 12408 KB Output is correct
21 Correct 175 ms 13168 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1624 KB Output is correct
2 Correct 14 ms 1624 KB Output is correct
3 Partially correct 151 ms 11328 KB Output is partially correct
4 Partially correct 168 ms 11572 KB Output is partially correct
5 Partially correct 155 ms 11880 KB Output is partially correct
6 Partially correct 201 ms 13112 KB Output is partially correct
7 Correct 134 ms 11776 KB Output is correct
8 Partially correct 137 ms 11556 KB Output is partially correct
9 Partially correct 167 ms 11868 KB Output is partially correct
10 Partially correct 189 ms 13108 KB Output is partially correct
11 Partially correct 190 ms 13216 KB Output is partially correct
12 Partially correct 183 ms 13112 KB Output is partially correct
13 Correct 152 ms 11232 KB Output is correct
14 Correct 133 ms 10276 KB Output is correct
15 Correct 150 ms 11236 KB Output is correct
16 Correct 130 ms 10276 KB Output is correct
17 Correct 168 ms 11232 KB Output is correct
18 Correct 154 ms 10296 KB Output is correct
19 Correct 183 ms 12460 KB Output is correct
20 Correct 194 ms 12684 KB Output is correct
21 Partially correct 190 ms 13096 KB Output is partially correct
22 Correct 192 ms 13096 KB Output is correct
23 Partially correct 200 ms 13100 KB Output is partially correct
24 Partially correct 203 ms 13100 KB Output is partially correct
25 Partially correct 186 ms 13108 KB Output is partially correct
26 Correct 179 ms 13092 KB Output is correct
27 Partially correct 112 ms 12436 KB Output is partially correct
28 Correct 108 ms 13048 KB Output is correct
29 Correct 109 ms 12552 KB Output is correct
30 Correct 111 ms 12340 KB Output is correct
31 Partially correct 114 ms 12300 KB Output is partially correct
32 Partially correct 104 ms 12236 KB Output is partially correct
33 Correct 115 ms 12964 KB Output is correct
34 Correct 127 ms 12256 KB Output is correct
35 Partially correct 109 ms 12244 KB Output is partially correct
36 Partially correct 111 ms 12196 KB Output is partially correct
37 Partially correct 114 ms 12420 KB Output is partially correct
38 Correct 125 ms 12536 KB Output is correct
39 Partially correct 168 ms 12920 KB Output is partially correct
40 Partially correct 166 ms 12740 KB Output is partially correct
41 Partially correct 178 ms 12876 KB Output is partially correct
42 Partially correct 178 ms 12752 KB Output is partially correct