oj.uz

Submission #1075007

# Submission time Handle Problem Language Result Execution time Memory
1075007 2024-08-25T17:30:54 Z 42kangaroo Highway Tolls (IOI18_highway) C++17
100 / 100
 212 ms 24268 KB 
//
// Created by 42kangaroo on 25/08/2024.
//
#include "bits/stdc++.h"
#include "highway.h"

using ll = long long;

using namespace std;
struct Ed {
	int to, i;
};
using g_t = vector<vector<Ed>>;

struct BfsVal {
	int to, i, d;
};

bool operator<(const BfsVal &l, const BfsVal &r) {
	return l.d < r.d;
}

void addDfs(int n, int p, g_t &g, vector<int> &dis, vector<BfsVal> &out) {
	for (auto e: g[n]) {
		if (e.to == p) continue;
		out.push_back({e.to, e.i, dis[e.to]});
		addDfs(e.to, n, g, dis, out);
	}
}

void wDfs(int n, int p, g_t &g, vector<int> &w) {
	for (auto e: g[n]) {
		if (e.to == p) continue;
		w[e.i] = 0;
		wDfs(e.to, n, g, w);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	vector<int> w(U.size(), 0);
	ll le = ask(w) / (ll) A;
	vector<bool> vis(N, false);
	g_t g(N);
	for (int i = 0; i < U.size(); ++i) {
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}
	int l = 0, r = U.size();
	while (l + 1 < r) {
		int m = (l + r) / 2;
		std::fill(w.begin(), w.end(), 1);
		for (int i = 0; i < m; ++i) {
			w[i] = 0;
		}
		if (ask(w) > le * A) l = m;
		else r = m;
	}
	vector<int> dis(N, -1);
	g_t gBfs(N);
	queue<BfsVal> q;
	q.push({U[l], -1, 0});
	q.push({V[l], -1, 0});
	while (!q.empty()) {
		auto bfV = q.front();
		q.pop();
		if (dis[bfV.to] != -1) continue;
		if (bfV.i >= 0) {
			gBfs[U[bfV.i]].push_back({V[bfV.i], bfV.i});
			gBfs[V[bfV.i]].push_back({U[bfV.i], bfV.i});
		}
		dis[bfV.to] = bfV.d;
		for (auto e: g[bfV.to]) {
			q.push({e.to, e.i, bfV.d + 1});
		}
	}
	vector<BfsVal> out;
	int x = U[l], y = V[l];
	addDfs(U[l], V[l], gBfs, dis, out);
	out.push_back({U[l], l, 0});
	std::sort(out.begin(), out.end());
	int ll = 0, rr = out.size();
	while (ll + 1 < rr) {
		int m = (ll + rr) / 2;
		std::fill(w.begin(), w.end(), 1);
		for (int i = 0; i < m; ++i) {
			w[out[i].i] = 0;
		}
		w[l] = 0;
		wDfs(V[l], U[l], gBfs, w);
		if (ask(w) > A * le) ll = m;
		else rr = m;
	}
	x = out[ll].to;
	out.clear();
	addDfs(V[l], U[l], gBfs, dis, out);
	out.push_back({V[l], l, 0});
	std::sort(out.begin(), out.end());
	ll = 0, rr = out.size();
	while (ll + 1 < rr) {
		int m = (ll + rr) / 2;
		std::fill(w.begin(), w.end(), 1);
		for (int i = 0; i < m; ++i) {
			w[out[i].i] = 0;
		}
		w[l] = 0;
		wDfs(U[l], V[l], gBfs, w);
		if (ask(w) > A * le) ll = m;
		else rr = m;
	}
	y = out[ll].to;
	answer(x, y);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < U.size(); ++i) {
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 1 ms 344 KB Output is correct
7 Correct 1 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 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 11 ms 2172 KB Output is correct
3 Correct 111 ms 15036 KB Output is correct
4 Correct 138 ms 15024 KB Output is correct
5 Correct 101 ms 15052 KB Output is correct
6 Correct 103 ms 15072 KB Output is correct
7 Correct 102 ms 15048 KB Output is correct
8 Correct 123 ms 15200 KB Output is correct
9 Correct 136 ms 14984 KB Output is correct
10 Correct 125 ms 15164 KB Output is correct
11 Correct 152 ms 15900 KB Output is correct
12 Correct 143 ms 17348 KB Output is correct
13 Correct 134 ms 16860 KB Output is correct
14 Correct 147 ms 17124 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2904 KB Output is correct
2 Correct 20 ms 4884 KB Output is correct
3 Correct 37 ms 8004 KB Output is correct
4 Correct 92 ms 19544 KB Output is correct
5 Correct 99 ms 20276 KB Output is correct
6 Correct 117 ms 22896 KB Output is correct
7 Correct 97 ms 24268 KB Output is correct
8 Correct 96 ms 20748 KB Output is correct
9 Correct 97 ms 22100 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 12 ms 2016 KB Output is correct
3 Correct 78 ms 12240 KB Output is correct
4 Correct 123 ms 15044 KB Output is correct
5 Correct 104 ms 15096 KB Output is correct
6 Correct 93 ms 15064 KB Output is correct
7 Correct 94 ms 15200 KB Output is correct
8 Correct 105 ms 14960 KB Output is correct
9 Correct 160 ms 14864 KB Output is correct
10 Correct 117 ms 15028 KB Output is correct
11 Correct 142 ms 16292 KB Output is correct
12 Correct 149 ms 17604 KB Output is correct
13 Correct 148 ms 16140 KB Output is correct
14 Correct 156 ms 16484 KB Output is correct
15 Correct 102 ms 15164 KB Output is correct
16 Correct 105 ms 15044 KB Output is correct
17 Correct 161 ms 16728 KB Output is correct
18 Correct 139 ms 17056 KB Output is correct
19 Correct 96 ms 15176 KB Output is correct
20 Correct 146 ms 18172 KB Output is correct
21 Correct 91 ms 16500 KB Output is correct
22 Correct 84 ms 16276 KB Output is correct
23 Correct 93 ms 15004 KB Output is correct
24 Correct 115 ms 15768 KB Output is correct
25 Correct 152 ms 23456 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2136 KB Output is correct
2 Correct 14 ms 2224 KB Output is correct
3 Correct 150 ms 14752 KB Output is correct
4 Correct 134 ms 15916 KB Output is correct
5 Correct 212 ms 15996 KB Output is correct
6 Correct 177 ms 16996 KB Output is correct
7 Correct 180 ms 16700 KB Output is correct
8 Correct 191 ms 16172 KB Output is correct
9 Correct 122 ms 11340 KB Output is correct
10 Correct 109 ms 11812 KB Output is correct
11 Correct 135 ms 13248 KB Output is correct
12 Correct 202 ms 14456 KB Output is correct
13 Correct 192 ms 16096 KB Output is correct
14 Correct 212 ms 15840 KB Output is correct
15 Correct 211 ms 16552 KB Output is correct
16 Correct 122 ms 12400 KB Output is correct
17 Correct 104 ms 16576 KB Output is correct
18 Correct 112 ms 16604 KB Output is correct
19 Correct 116 ms 16704 KB Output is correct
20 Correct 130 ms 16592 KB Output is correct
21 Correct 200 ms 17192 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1880 KB Output is correct
2 Correct 12 ms 2212 KB Output is correct
3 Correct 114 ms 15540 KB Output is correct
4 Correct 183 ms 14920 KB Output is correct
5 Correct 150 ms 15784 KB Output is correct
6 Correct 197 ms 16688 KB Output is correct
7 Correct 153 ms 15540 KB Output is correct
8 Correct 165 ms 14880 KB Output is correct
9 Correct 139 ms 15904 KB Output is correct
10 Correct 180 ms 16804 KB Output is correct
11 Correct 170 ms 16128 KB Output is correct
12 Correct 172 ms 16908 KB Output is correct
13 Correct 99 ms 13280 KB Output is correct
14 Correct 110 ms 11364 KB Output is correct
15 Correct 101 ms 13276 KB Output is correct
16 Correct 108 ms 11448 KB Output is correct
17 Correct 103 ms 13432 KB Output is correct
18 Correct 101 ms 11380 KB Output is correct
19 Correct 161 ms 14508 KB Output is correct
20 Correct 166 ms 15192 KB Output is correct
21 Correct 177 ms 16500 KB Output is correct
22 Correct 207 ms 16232 KB Output is correct
23 Correct 185 ms 15780 KB Output is correct
24 Correct 181 ms 16468 KB Output is correct
25 Correct 181 ms 15892 KB Output is correct
26 Correct 178 ms 16748 KB Output is correct
27 Correct 95 ms 16584 KB Output is correct
28 Correct 114 ms 16760 KB Output is correct
29 Correct 99 ms 16888 KB Output is correct
30 Correct 109 ms 16672 KB Output is correct
31 Correct 95 ms 16668 KB Output is correct
32 Correct 126 ms 16324 KB Output is correct
33 Correct 114 ms 16760 KB Output is correct
34 Correct 100 ms 16616 KB Output is correct
35 Correct 98 ms 16372 KB Output is correct
36 Correct 121 ms 16600 KB Output is correct
37 Correct 113 ms 16772 KB Output is correct
38 Correct 92 ms 16564 KB Output is correct
39 Correct 204 ms 17752 KB Output is correct
40 Correct 196 ms 18044 KB Output is correct
41 Correct 184 ms 16860 KB Output is correct
42 Correct 183 ms 16016 KB Output is correct