oj.uz

Submission #587301

# Submission time Handle Problem Language Result Execution time Memory
587301 2022-07-01T15:39:37 Z kamelfanger83 Highway Tolls (IOI18_highway) C++14
51 / 100
 145 ms 26220 KB 
#include <iostream>
#include <vector>
#include "highway.h"
#include <cassert>

#define int long long

using namespace std;

vector<vector<pair<int, int>>> cons;
vector<signed> w;

void dfs(int i, int from, int d, vector<vector<pair<int, int>>>& put){
  for(pair<int, int> p : cons[i]){
    int c = p.first, m = p.second;
    if(c == from) continue;
    put[d+1].push_back({c, m});
    w[m] = 1;
    dfs(c, i, d+1, put);
  }
}

void find_pair(signed N, vector<signed> U, vector<signed> V, signed A, signed B) {
  int M = U.size();
  cons = vector<vector<pair<int, int>>> (N); 
  for(int m = 0; m < M; m++){
    cons[U[m]].push_back({V[m], m});
    cons[V[m]].push_back({U[m], m});
  }

  int dst = ask(vector<signed> (M))/A;
  auto qrange = [&](int ll, int rl){
    vector<signed> wl(M);
    for(int i = ll; i < rl; i++) wl[i] = 1;
    return ask(wl) != dst*A;
  };

  int l = 0, r = M;
  while(l + 1 < r){
    int m = l + (r-l)/2;
    if(qrange(l, m)) r = m;
    else l = m;
  }

  vector<vector<pair<int, int>>> side1 (N);
  vector<vector<pair<int, int>>> side2 (N);
  w = vector<signed>(M);
  dfs(U[l], V[l], 0, side1);
  w = vector<signed>(M);
  dfs(V[l], U[l], 0, side2);
  int dst2 = (ask(w)-dst*A)/(B-A);

  auto bs_sel = [&](vector<pair<int, int>> sel){
    int l = 0, r = sel.size();
    while(l + 1 < r){
      int m = l + (r-l)/2;
      vector<signed> lw (M);
      for(int set = l; set < m; set++) lw[sel[set].second] = 1;
      if(ask(lw) != dst*A) r = m;
      else l = m;
    }
    return sel[l].first;
  };

  int u, s;
  if(dst2 > 0) u = bs_sel(side2[dst2]);
  else u = V[l];
  if(dst-dst2-1 > 0) s = bs_sel(side1[dst-dst2-1]);
  else s = U[l];
  answer(u, s);
}

/*
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>

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;
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 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 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 10 ms 1908 KB Output is correct
3 Correct 144 ms 15532 KB Output is correct
4 Correct 129 ms 15676 KB Output is correct
5 Correct 139 ms 15572 KB Output is correct
6 Correct 128 ms 15220 KB Output is correct
7 Correct 133 ms 15560 KB Output is correct
8 Correct 132 ms 15436 KB Output is correct
9 Correct 101 ms 15324 KB Output is correct
10 Correct 116 ms 15372 KB Output is correct
11 Correct 103 ms 17772 KB Output is correct
12 Correct 109 ms 19168 KB Output is correct
13 Correct 108 ms 18220 KB Output is correct
14 Correct 104 ms 18704 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3024 KB Output is correct
2 Correct 19 ms 5708 KB Output is correct
3 Correct 29 ms 8624 KB Output is correct
4 Correct 96 ms 22572 KB Output is correct
5 Correct 91 ms 22476 KB Output is correct
6 Correct 93 ms 24368 KB Output is correct
7 Correct 80 ms 26220 KB Output is correct
8 Correct 84 ms 23276 KB Output is correct
9 Correct 85 ms 23760 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 10 ms 1908 KB Output is correct
3 Correct 75 ms 12100 KB Output is correct
4 Correct 107 ms 15172 KB Output is correct
5 Correct 138 ms 15516 KB Output is correct
6 Correct 91 ms 15372 KB Output is correct
7 Correct 108 ms 15536 KB Output is correct
8 Correct 92 ms 15224 KB Output is correct
9 Correct 137 ms 15832 KB Output is correct
10 Correct 104 ms 15488 KB Output is correct
11 Correct 102 ms 17808 KB Output is correct
12 Correct 145 ms 19256 KB Output is correct
13 Correct 128 ms 18656 KB Output is correct
14 Correct 127 ms 18528 KB Output is correct
15 Correct 92 ms 15448 KB Output is correct
16 Correct 107 ms 14940 KB Output is correct
17 Correct 120 ms 18324 KB Output is correct
18 Correct 112 ms 18736 KB Output is correct
19 Correct 98 ms 15484 KB Output is correct
20 Correct 138 ms 19828 KB Output is correct
21 Correct 127 ms 16188 KB Output is correct
22 Correct 86 ms 15724 KB Output is correct
23 Correct 107 ms 15700 KB Output is correct
24 Correct 128 ms 16156 KB Output is correct
25 Correct 144 ms 25704 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 7504 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 6792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -