oj.uz

Submission #785893

# Submission time Handle Problem Language Result Execution time Memory
785893 2023-07-17T18:03:41 Z esomer Highway Tolls (IOI18_highway) C++17
51 / 100
 131 ms 21096 KB 
#include<bits/stdc++.h>
#include "highway.h"

using namespace std;

typedef long long ll;

//~ ll ask(vector<int> w);
//~ void answer(int s, int t);

void DFS(int x, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& pr, vector<vector<int>>& depth, int p, int edge, int d){
	pr[x] = {p, edge};
	depth[d].push_back(x);
	for(pair<int, int> pr2 : adj[x]){
		int node = pr2.first;
		int e = pr2.second;
		if(node != p) DFS(node, adj, pr, depth, x, e, d + 1);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	int n = N;
	int m = (int)U.size();
	if(m != n - 1) {answer(0, 1); return;}
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i++){
		int a = U[i]; int b = V[i];
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
	}
	vector<pair<int, int>> p(n);
	vector<vector<int>> depth(n);
	DFS(0, adj, p, depth, -1, -1, 0);
	vector<int> w(m, 0);
	ll dist = ask(w) / A;
	//Now I want to find the depth of the lowest node in the tree.
	int lo = 0;
	int hi = n-1;
	int bst;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		w.assign(m, 0);
		for(int i = 0; i <= mid; i++){
			for(int x : depth[i]){
				if(x == 0) continue;
				w[p[x].second] = 1;
			}
		}
		ll d = ask(w);
		if(d == dist * B){
			bst = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	lo = 0;
	hi = (int)depth[bst].size() - 1;
	int s;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		w.assign(m, 0);
		for(int i = lo; i <= mid; i++){
			int x = depth[bst][i];
			if(x == 0) continue;
			w[p[x].second] = 1;
		}
		ll d = ask(w);
		if(d != dist * A){
			s = depth[bst][mid];
			hi = mid - 1;
		}else lo = mid + 1;
	}
	w.assign(m, 0);
	int curr_node = s;
	while(p[curr_node].second != -1){
		w[p[curr_node].second] = 1;
		curr_node = p[curr_node].first;
	}
	ll dist2 = ask(w);
	ll depth_anc = bst - ((dist2 - dist * A) / (B-A));
	ll bst2 = dist - bst + 2 * depth_anc;
	if(bst - bst2 == dist){
		int curr_node = s;
		int curr_depth = bst;
		while(curr_node != -1){
			if(curr_depth == bst2){
				answer(s, curr_node); return;
			}
			curr_node = p[curr_node].first;
			curr_depth--;
		}
	}
	lo = 0;
	hi = (int)depth[bst2].size() - 1;
	int t;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		vector<int> added;
		for(int i = lo; i <= mid; i++){
			int x = depth[bst2][i];
			if(x == 0 || w[p[x].second] == 1) continue;
			w[p[x].second] = 1;
			added.push_back(p[x].second);
		}
		ll d = ask(w);
		if(d != dist2){
			t = depth[bst2][mid];
			hi = mid - 1;
		}else lo = mid + 1;
		for(int x : added) w[x] = 0;
	}
	answer(s, t);
	return;
}

//~ namespace {

//~ constexpr int MAX_NUM_CALLS = 100;
//~ constexpr long long INF = 1LL << 61;

//~ int N, M, A, B, S, T;
//~ std::vector<int> U, V;
//~ std::vector<std::vector<std::pair<int, int>>> graph;

//~ bool answered, wrong_pair;
//~ int num_calls;

//~ int read_int() {
  //~ int x;
  //~ if (scanf("%d", &x) != 1) {
    //~ fprintf(stderr, "Error while reading input\n");
    //~ exit(1);
  //~ }
  //~ return x;
//~ }

//~ void wrong_answer(const char *MSG) {
  //~ printf("Wrong Answer: %s\n", MSG);
  //~ exit(0);
//~ }

//~ }  // namespace

//~ long long ask(const std::vector<int> &w) {
  //~ if (++num_calls > MAX_NUM_CALLS) {
    //~ wrong_answer("more than 100 calls to ask");
  //~ }
  //~ if (w.size() != (size_t)M) {
    //~ wrong_answer("w is invalid");
  //~ }
  //~ for (size_t i = 0; i < w.size(); ++i) {
    //~ if (!(w[i] == 0 || w[i] == 1)) {
      //~ wrong_answer("w is invalid");
    //~ }
  //~ }

  //~ std::vector<bool> visited(N, false);
  //~ std::vector<long long> current_dist(N, INF);
  //~ std::queue<int> qa, qb;
  //~ qa.push(S);
  //~ current_dist[S] = 0;
  //~ while (!qa.empty() || !qb.empty()) {
    //~ int v;
    //~ if (qb.empty() ||
        //~ (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      //~ v = qa.front();
      //~ qa.pop();
    //~ } else {
      //~ v = qb.front();
      //~ qb.pop();
    //~ }
    //~ if (visited[v]) {
      //~ continue;
    //~ }
    //~ visited[v] = true;
    //~ long long d = current_dist[v];
    //~ if (v == T) {
      //~ return d;
    //~ }
    //~ for (auto e : graph[v]) {
      //~ int vv = e.first;
      //~ int ei = e.second;
      //~ if (!visited[vv]) {
        //~ if (w[ei] == 0) {
          //~ if (current_dist[vv] > d + A) {
            //~ current_dist[vv] = d + A;
            //~ qa.push(vv);
          //~ }
        //~ } else {
          //~ if (current_dist[vv] > d + B) {
            //~ current_dist[vv] = d + B;
            //~ qb.push(vv);
          //~ }
        //~ }
      //~ }
    //~ }
  //~ }
  //~ return -1;
//~ }

//~ void answer(int s, int t) {
  //~ if (answered) {
    //~ wrong_answer("answered not exactly once");
  //~ }

  //~ if (!((s == S && t == T) || (s == T && t == S))) {
    //~ wrong_pair = true;
  //~ }

  //~ answered = true;
//~ }

//~ int main() {
  //~ N = read_int();
  //~ M = read_int();
  //~ A = read_int();
  //~ B = read_int();
  //~ S = read_int();
  //~ T = read_int();
  //~ U.resize(M);
  //~ V.resize(M);
  //~ graph.assign(N, std::vector<std::pair<int, int>>());
  //~ for (int i = 0; i < M; ++i) {
    //~ U[i] = read_int();
    //~ V[i] = read_int();
    //~ graph[U[i]].push_back({V[i], i});
    //~ graph[V[i]].push_back({U[i], i});
  //~ }

  //~ answered = false;
  //~ wrong_pair = false;
  //~ num_calls = 0;
  //~ find_pair(N, U, V, A, B);
  //~ if (!answered) {
    //~ wrong_answer("answered not exactly once");
  //~ }
  //~ if (wrong_pair) {
    //~ wrong_answer("{s, t} is wrong");
  //~ }
  //~ printf("Accepted: %d\n", num_calls);
  //~ return 0;
//~ }

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:111:8: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |  answer(s, t);
      |  ~~~~~~^~~~~~
highway.cpp:86:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     answer(s, curr_node); return;
      |     ~~~~~~^~~~~~~~~~~~~~
highway.cpp:56:21: warning: 'bst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |  hi = (int)depth[bst].size() - 1;
      |                     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 10 ms 1492 KB Output is correct
3 Correct 74 ms 10884 KB Output is correct
4 Correct 122 ms 10916 KB Output is correct
5 Correct 85 ms 10916 KB Output is correct
6 Correct 76 ms 10872 KB Output is correct
7 Correct 73 ms 10932 KB Output is correct
8 Correct 81 ms 11028 KB Output is correct
9 Correct 93 ms 10940 KB Output is correct
10 Correct 123 ms 10920 KB Output is correct
11 Correct 111 ms 12732 KB Output is correct
12 Correct 117 ms 13960 KB Output is correct
13 Correct 122 ms 13088 KB Output is correct
14 Correct 108 ms 12016 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2512 KB Output is correct
2 Correct 23 ms 4808 KB Output is correct
3 Correct 28 ms 7188 KB Output is correct
4 Correct 72 ms 21092 KB Output is correct
5 Correct 97 ms 21080 KB Output is correct
6 Correct 84 ms 21088 KB Output is correct
7 Correct 104 ms 21096 KB Output is correct
8 Correct 74 ms 21080 KB Output is correct
9 Correct 94 ms 21096 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1508 KB Output is correct
3 Correct 60 ms 8540 KB Output is correct
4 Correct 77 ms 10852 KB Output is correct
5 Correct 98 ms 10916 KB Output is correct
6 Correct 95 ms 10904 KB Output is correct
7 Correct 82 ms 10908 KB Output is correct
8 Correct 109 ms 10892 KB Output is correct
9 Correct 107 ms 10900 KB Output is correct
10 Correct 114 ms 10900 KB Output is correct
11 Correct 123 ms 11832 KB Output is correct
12 Correct 113 ms 13976 KB Output is correct
13 Correct 106 ms 13132 KB Output is correct
14 Correct 103 ms 13880 KB Output is correct
15 Correct 65 ms 10916 KB Output is correct
16 Correct 92 ms 10896 KB Output is correct
17 Correct 125 ms 13464 KB Output is correct
18 Correct 115 ms 12680 KB Output is correct
19 Correct 107 ms 10880 KB Output is correct
20 Correct 105 ms 14776 KB Output is correct
21 Correct 96 ms 11340 KB Output is correct
22 Correct 116 ms 11336 KB Output is correct
23 Correct 66 ms 11244 KB Output is correct
24 Correct 131 ms 12400 KB Output is correct
25 Correct 109 ms 19400 KB Output is correct

Subtask #5
0 / 18.0

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