oj.uz

Submission #587299

# Submission time Handle Problem Language Result Execution time Memory
587299 2022-07-01T15:38:19 Z jasmin Highway Tolls (IOI18_highway) C++14
51 / 100
 145 ms 26224 KB 
#include <iostream>
#include <vector>
#include "highway.h"
 
#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))/(int)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*(int)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*(int)A)/(int)(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*(int)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);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 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 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 308 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 464 KB Output is correct
2 Correct 10 ms 1912 KB Output is correct
3 Correct 106 ms 15452 KB Output is correct
4 Correct 97 ms 15684 KB Output is correct
5 Correct 92 ms 15636 KB Output is correct
6 Correct 99 ms 15196 KB Output is correct
7 Correct 98 ms 15652 KB Output is correct
8 Correct 102 ms 15452 KB Output is correct
9 Correct 132 ms 15344 KB Output is correct
10 Correct 92 ms 15432 KB Output is correct
11 Correct 140 ms 17632 KB Output is correct
12 Correct 143 ms 19104 KB Output is correct
13 Correct 104 ms 18192 KB Output is correct
14 Correct 134 ms 18716 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3056 KB Output is correct
2 Correct 17 ms 5696 KB Output is correct
3 Correct 28 ms 8520 KB Output is correct
4 Correct 86 ms 22352 KB Output is correct
5 Correct 92 ms 22448 KB Output is correct
6 Correct 84 ms 24436 KB Output is correct
7 Correct 86 ms 26224 KB Output is correct
8 Correct 93 ms 23384 KB Output is correct
9 Correct 92 ms 23764 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 2000 KB Output is correct
3 Correct 96 ms 12056 KB Output is correct
4 Correct 101 ms 15272 KB Output is correct
5 Correct 122 ms 15532 KB Output is correct
6 Correct 92 ms 15320 KB Output is correct
7 Correct 89 ms 15532 KB Output is correct
8 Correct 92 ms 15224 KB Output is correct
9 Correct 93 ms 15828 KB Output is correct
10 Correct 106 ms 15504 KB Output is correct
11 Correct 143 ms 17824 KB Output is correct
12 Correct 143 ms 19200 KB Output is correct
13 Correct 104 ms 18632 KB Output is correct
14 Correct 103 ms 18568 KB Output is correct
15 Correct 102 ms 15432 KB Output is correct
16 Correct 88 ms 14940 KB Output is correct
17 Correct 140 ms 18268 KB Output is correct
18 Correct 145 ms 18672 KB Output is correct
19 Correct 95 ms 15468 KB Output is correct
20 Correct 133 ms 19680 KB Output is correct
21 Correct 98 ms 16192 KB Output is correct
22 Correct 107 ms 15812 KB Output is correct
23 Correct 126 ms 15580 KB Output is correct
24 Correct 107 ms 16176 KB Output is correct
25 Correct 119 ms 25688 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 7448 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 20 ms 6828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -