oj.uz

Submission #778115

# Submission time Handle Problem Language Result Execution time Memory
778115 2023-07-10T06:25:55 Z NeroZein Highway Tolls (IOI18_highway) C++17
0 / 100
 205 ms 262144 KB 
#include "highway.h"
#include "bits/stdc++.h"
using namespace std; 

int n, m;
vector<int> pe;
vector<int> dep;
vector<vector<pair<int,int>>> g; 

void Dfs (int v, int p) {
  for (auto [u, i] : g[v]) {
    if (u == p) {
      continue;
    }
    pe[u] = i; 
    dep[u] = dep[v] + 1; 
    Dfs(u, v); 
  }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  n = N;
  g.resize(n); 
  pe.resize(n); 
  dep.resize(n); 
  m = (int) U.size(); 
  for (int i = 0; i < m; ++i) {
    g[U[i]].push_back({V[i], i});
    g[V[i]].push_back({U[i], i});
  }
  Dfs(0, 0); 
  vector<int> vec; 
  auto fix = [&](vector<int> nodes) {
    vector<int> ret(m);
    for (int u : nodes) {
      ret[pe[u]] = true; 
    }
    return ret;
  }; 
  int dis = ask({}); 
  int depT = dis / A;
  assert(depT != 0); 
  for (int i = 0; i < n; ++i) {
    if (dep[i] == depT) {
      vec.push_back(i); 
    }
  }
  while (vec.size() > 1) {
    vector<int> lx, rx;
    int mid = (int) vec.size() / 2;
    for (int i = 0; i < mid; ++i) {
      lx.push_back(vec[i]);
    }
    for (int i = mid; i < (int) vec.size(); ++i) {
      rx.push_back(vec[i]); 
    }
    if (ask(fix(lx)) > dis) {
      vec = lx;
    } else {
      vec = rx; 
    }
  }
  assert(!vec.empty());
  answer(0, vec[0]);//S, T
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1488 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 178 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -