oj.uz

Submission #1074999

# Submission time Handle Problem Language Result Execution time Memory
1074999 2024-08-25T17:27:30 Z 42kangaroo Highway Tolls (IOI18_highway) C++17
7 / 100
 172 ms 17292 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);
	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;
	}
	if (!out.empty())
		x = out[ll].to;
	out.clear();
	addDfs(V[l], U[l], gBfs, dis, out);
	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;
	}
	if (!out.empty())
		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
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 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 10 ms 2136 KB Output is correct
3 Correct 128 ms 15032 KB Output is correct
4 Correct 111 ms 15036 KB Output is correct
5 Correct 98 ms 15028 KB Output is correct
6 Correct 105 ms 15044 KB Output is correct
7 Correct 101 ms 15064 KB Output is correct
8 Correct 114 ms 14984 KB Output is correct
9 Correct 119 ms 15052 KB Output is correct
10 Correct 113 ms 15288 KB Output is correct
11 Correct 162 ms 15996 KB Output is correct
12 Correct 145 ms 17292 KB Output is correct
13 Correct 129 ms 16820 KB Output is correct
14 Correct 133 ms 17104 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2904 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 12 ms 2136 KB Output is correct
3 Correct 77 ms 12216 KB Output is correct
4 Correct 118 ms 15028 KB Output is correct
5 Incorrect 97 ms 14972 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2132 KB Output is correct
2 Correct 13 ms 2136 KB Output is correct
3 Correct 157 ms 14688 KB Output is correct
4 Correct 120 ms 16012 KB Output is correct
5 Incorrect 172 ms 16136 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1880 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -