oj.uz

Submission #778093

# Submission time Handle Problem Language Result Execution time Memory
778093 2023-07-10T06:11:59 Z NeroZein Highway Tolls (IOI18_highway) C++17
5 / 100
 193 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; 
  vector<int> w(m, 0); 
  int dis = ask(w); 
  int depT = dis / A;
  for (int i = 0; i < n; ++i) {
    if (dep[i] == depT) {
      vec.push_back(i); 
    }
  }
  auto fix = [&](vector<int> nodes) {
    vector<int> ret(m);
    for (int u : nodes) {
      ret[pe[u]] = true; 
    }
    return ret;
  }; 
  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; 
    }
  }
  answer(0, vec[0]);//S, T
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 276 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 6 ms 1148 KB Output is correct
3 Correct 89 ms 8664 KB Output is correct
4 Correct 72 ms 8836 KB Output is correct
5 Correct 66 ms 8680 KB Output is correct
6 Correct 63 ms 8628 KB Output is correct
7 Correct 73 ms 8672 KB Output is correct
8 Correct 76 ms 8708 KB Output is correct
9 Correct 73 ms 8612 KB Output is correct
10 Correct 68 ms 8704 KB Output is correct
11 Correct 49 ms 9048 KB Output is correct
12 Correct 72 ms 9496 KB Output is correct
13 Correct 56 ms 9088 KB Output is correct
14 Incorrect 80 ms 8672 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1536 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 1 ms 388 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 Runtime error 193 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 177 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -