oj.uz

Submission #1021926

# Submission time Handle Problem Language Result Execution time Memory
1021926 2024-07-13T07:40:48 Z fv3 Highway Tolls (IOI18_highway) C++14
12 / 100
 77 ms 8100 KB 
#include <bits/stdc++.h>	
#include "highway.h"
 
using namespace std;
typedef long long ll;

int edgeCnt;
vector<vector<pair<int, int>>> adj;

int bfs_dist;
vector<pair<int, int>> sus_edges;
void find_sus_edges(int index, int last, int dist)
{
	dist += 1;

	for (auto node : adj[index])
	{
		if (node.first == last) continue;
		if (dist == bfs_dist)
			sus_edges.push_back(node);
		else
			find_sus_edges(node.first, index, dist);
	}
}

int find_T(int root, ll dist)
{
	find_sus_edges(root, root, 0);

	int l = 0, r = sus_edges.size() - 1;
	while (l < r)
	{
		int c = (l + r + 1) / 2;

		vector<int> w(edgeCnt);
		for (int i = c; i <= r; i++)
			w[sus_edges[i].second] = 1;

		ll cur_dist = ask(w);
		if (cur_dist == dist)
			r = c - 1;
		else
			l = c;
	}

	return sus_edges[l].first;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) 
{
	edgeCnt = U.size();
	adj = vector<vector<pair<int, int>>>(N);
	for (int i = 0; i < edgeCnt; i++)
	{
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}

	int S = 0;
	ll dist = ask(vector<int>(edgeCnt));
	bfs_dist = dist / A;

	int T = find_T(S, dist);

	//cerr << "Guess: S = " << S << ", T = " << T << '\n';

	answer(S, T);
}

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 1 ms 340 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 1 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 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 7 ms 1172 KB Output is correct
3 Correct 77 ms 7692 KB Output is correct
4 Correct 73 ms 7696 KB Output is correct
5 Correct 66 ms 7920 KB Output is correct
6 Correct 61 ms 7736 KB Output is correct
7 Correct 72 ms 7788 KB Output is correct
8 Correct 68 ms 7900 KB Output is correct
9 Correct 73 ms 7676 KB Output is correct
10 Correct 63 ms 7676 KB Output is correct
11 Correct 59 ms 7424 KB Output is correct
12 Correct 61 ms 7920 KB Output is correct
13 Correct 57 ms 7768 KB Output is correct
14 Correct 72 ms 8100 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1112 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 Incorrect 0 ms 344 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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