oj.uz

Submission #390732

# Submission time Handle Problem Language Result Execution time Memory
390732 2021-04-16T19:38:59 Z JimmyZJX Highway Tolls (IOI18_highway) C++14
90 / 100
 301 ms 12712 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>

#include "highway.h"

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

#define MAXMN 130003

vector<vector<pair<int, int>>> nbs(MAXMN); // {nb, edgeNo}
vector<int> parent(MAXMN);
vector<int> parentEdge(MAXMN);
Vi edgeSorted;
Vi edgeRank;
int maxDist;

int parentOf(int n1, int n2) {
	if (parent[n1] == n2) return n2;
	return n1;
}

int childOf(int n1, int n2) {
	if (parent[n1] == n2) return n1;
	return n2;
}

int largestEdgeOfRank(int r) {
	forR(i, edgeSorted.size()) {
		if (edgeRank[edgeSorted[i]] > r)
			return i > 0 ? i - 1 : i;
	}
	return edgeSorted.size() - 1;
}

void build_tree(int root) {
	Vb vis(MAXMN); Vb edgeVis(MAXMN);
	edgeSorted.clear(); edgeRank = Vi(MAXMN); maxDist = 0;
	queue<pair<int, int>> q; q.push({ root, 0 }); // nodeNo, level
	vis[root] = true;
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		int x = p.first, level = p.second;
		maxDist = max(maxDist, level);
		for (auto nbP : nbs[x]) {
			int nb = nbP.first, nbEdge = nbP.second;
			if (!vis[nb]) {
				vis[nb] = true;
				q.push({ nb, level + 1 });
				parent[nb] = x; parentEdge[nb] = nbEdge;
			}
			if (!edgeVis[nbEdge]) {
				edgeVis[nbEdge] = true;
				edgeSorted.push_back(nbEdge);
				edgeRank[nbEdge] = level + 1;
			}
		}
	}
}

void find_pair(int N, Vi U, Vi V, int A, int B) {
	int m = U.size();

	forR(i, m) {
		nbs[U[i]].push_back({ V[i], i });
		nbs[V[i]].push_back({ U[i], i });
	}

	build_tree(N / 4);

	LL minCost = ask(Vi(m));
	LL dist = minCost / A;
	// search for range of edges
	int l = 0, r = m - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		Vi ws(m);
		for (int i = 0; i <= mid; i++) ws[edgeSorted[i]] = 1;
		if (ask(ws) == minCost) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	int leftEdge = edgeSorted[l];
	int rootNode = parentOf(U[leftEdge], V[leftEdge]);

	build_tree(rootNode);

	l = 0, r = largestEdgeOfRank(dist);
	while (l < r) {
		int mid = (l + r) / 2;
		Vi ws(m);
		for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1;
		if (ask(ws) == minCost) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	int rightRank = l;
	int rightEdge = edgeSorted[l];

	int rightChild = childOf(U[rightEdge], V[rightEdge]);

	LL distR = 0; Vi REdges;
	for (int n = rightChild; n != rootNode; n = parent[n]) {
		REdges.push_back(parentEdge[n]);
		distR++;
	}
	LL distL = dist - distR;
	if (distL == 0) {
		answer(rootNode, rightChild);
		return;
	}

	l = 0, r = min(rightRank, largestEdgeOfRank(distL));
	while (l < r) {
		int mid = (l + r) / 2;
		Vi ws(m);
		for (int i = mid + 1; i <= m - 1; i++) ws[edgeSorted[i]] = 1;
		for (int e : REdges) ws[e] = 0;
		if (ask(ws) == minCost) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	int edgeLeft = edgeSorted[l];
	int leftChild = childOf(U[edgeLeft], V[edgeLeft]);

	answer(leftChild, rightChild);
}

Compilation message

highway.cpp: In function 'int largestEdgeOfRank(int)':
highway.cpp:26:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define forR(i, n) for (int i = 0; i < (n); i++)
      |                                      ^
highway.cpp:48:2: note: in expansion of macro 'forR'
   48 |  forR(i, edgeSorted.size()) {
      |  ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5320 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 4 ms 5320 KB Output is correct
4 Correct 5 ms 5440 KB Output is correct
5 Correct 4 ms 5448 KB Output is correct
6 Correct 4 ms 5436 KB Output is correct
7 Correct 4 ms 5448 KB Output is correct
8 Correct 4 ms 5320 KB Output is correct
9 Correct 4 ms 5320 KB Output is correct
10 Correct 4 ms 5436 KB Output is correct
11 Correct 4 ms 5320 KB Output is correct
12 Correct 5 ms 5320 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5492 KB Output is correct
2 Correct 19 ms 5944 KB Output is correct
3 Correct 208 ms 10884 KB Output is correct
4 Correct 191 ms 11076 KB Output is correct
5 Correct 173 ms 10916 KB Output is correct
6 Correct 182 ms 10860 KB Output is correct
7 Correct 202 ms 10932 KB Output is correct
8 Correct 152 ms 10948 KB Output is correct
9 Correct 145 ms 10904 KB Output is correct
10 Correct 161 ms 10852 KB Output is correct
11 Correct 146 ms 10460 KB Output is correct
12 Correct 203 ms 10448 KB Output is correct
13 Correct 196 ms 10284 KB Output is correct
14 Correct 198 ms 10248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5960 KB Output is correct
2 Correct 38 ms 6464 KB Output is correct
3 Correct 47 ms 7064 KB Output is correct
4 Correct 113 ms 10332 KB Output is correct
5 Correct 175 ms 10388 KB Output is correct
6 Correct 114 ms 10344 KB Output is correct
7 Correct 100 ms 10288 KB Output is correct
8 Correct 151 ms 10236 KB Output is correct
9 Correct 158 ms 10216 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5448 KB Output is correct
2 Correct 20 ms 6048 KB Output is correct
3 Correct 142 ms 9748 KB Output is correct
4 Correct 202 ms 10900 KB Output is correct
5 Correct 169 ms 10972 KB Output is correct
6 Correct 189 ms 10884 KB Output is correct
7 Correct 182 ms 10944 KB Output is correct
8 Correct 186 ms 10844 KB Output is correct
9 Correct 201 ms 10900 KB Output is correct
10 Correct 153 ms 10968 KB Output is correct
11 Correct 167 ms 10424 KB Output is correct
12 Correct 205 ms 10376 KB Output is correct
13 Correct 151 ms 10280 KB Output is correct
14 Correct 198 ms 10320 KB Output is correct
15 Correct 141 ms 10884 KB Output is correct
16 Correct 185 ms 10840 KB Output is correct
17 Correct 152 ms 10344 KB Output is correct
18 Correct 210 ms 10332 KB Output is correct
19 Correct 145 ms 10844 KB Output is correct
20 Correct 141 ms 10260 KB Output is correct
21 Correct 169 ms 11092 KB Output is correct
22 Correct 173 ms 11016 KB Output is correct
23 Correct 189 ms 11352 KB Output is correct
24 Correct 187 ms 11240 KB Output is correct
25 Correct 161 ms 10432 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5980 KB Output is correct
2 Correct 22 ms 6156 KB Output is correct
3 Correct 193 ms 11192 KB Output is correct
4 Correct 194 ms 11612 KB Output is correct
5 Correct 301 ms 12464 KB Output is correct
6 Correct 277 ms 12492 KB Output is correct
7 Correct 279 ms 12472 KB Output is correct
8 Correct 239 ms 12596 KB Output is correct
9 Correct 232 ms 11108 KB Output is correct
10 Correct 173 ms 11636 KB Output is correct
11 Correct 190 ms 11436 KB Output is correct
12 Correct 268 ms 12268 KB Output is correct
13 Correct 230 ms 12408 KB Output is correct
14 Correct 284 ms 12472 KB Output is correct
15 Correct 216 ms 12712 KB Output is correct
16 Correct 261 ms 11956 KB Output is correct
17 Correct 147 ms 11084 KB Output is correct
18 Correct 192 ms 11408 KB Output is correct
19 Correct 190 ms 11244 KB Output is correct
20 Correct 170 ms 11452 KB Output is correct
21 Correct 282 ms 12420 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5976 KB Output is correct
2 Correct 22 ms 6216 KB Output is correct
3 Correct 221 ms 10988 KB Output is correct
4 Correct 228 ms 11236 KB Output is correct
5 Correct 215 ms 11532 KB Output is correct
6 Correct 265 ms 12500 KB Output is correct
7 Correct 192 ms 11004 KB Output is correct
8 Correct 236 ms 11188 KB Output is correct
9 Correct 172 ms 11460 KB Output is correct
10 Correct 258 ms 12504 KB Output is correct
11 Correct 275 ms 12532 KB Output is correct
12 Correct 248 ms 12616 KB Output is correct
13 Correct 178 ms 11448 KB Output is correct
14 Correct 200 ms 11644 KB Output is correct
15 Correct 226 ms 11448 KB Output is correct
16 Correct 184 ms 11564 KB Output is correct
17 Correct 272 ms 11508 KB Output is correct
18 Correct 190 ms 11696 KB Output is correct
19 Correct 276 ms 12260 KB Output is correct
20 Correct 214 ms 12392 KB Output is correct
21 Correct 300 ms 12596 KB Output is correct
22 Correct 210 ms 12476 KB Output is correct
23 Correct 277 ms 12444 KB Output is correct
24 Correct 296 ms 12480 KB Output is correct
25 Correct 293 ms 12468 KB Output is correct
26 Correct 282 ms 12488 KB Output is correct
27 Correct 145 ms 11596 KB Output is correct
28 Correct 192 ms 11232 KB Output is correct
29 Correct 146 ms 11644 KB Output is correct
30 Correct 142 ms 11484 KB Output is correct
31 Correct 150 ms 11396 KB Output is correct
32 Partially correct 155 ms 11368 KB Output is partially correct
33 Correct 196 ms 11248 KB Output is correct
34 Correct 181 ms 11124 KB Output is correct
35 Correct 149 ms 11520 KB Output is correct
36 Correct 189 ms 11304 KB Output is correct
37 Correct 198 ms 11192 KB Output is correct
38 Correct 188 ms 11364 KB Output is correct
39 Correct 205 ms 12400 KB Output is correct
40 Correct 214 ms 12472 KB Output is correct
41 Partially correct 263 ms 12472 KB Output is partially correct
42 Correct 277 ms 12388 KB Output is correct