oj.uz

Submission #964879

# Submission time Handle Problem Language Result Execution time Memory
964879 2024-04-17T16:53:49 Z TAhmed33 Highway Tolls (IOI18_highway) C++17
18 / 100
 121 ms 20100 KB 
#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r) {
  return uniform_int_distribution <int> (l, r) (rng);
}
vector <pair <int, int>> adj[MAXN];
vector <int> ett, ett2;
int in[MAXN], out[MAXN], dep[MAXN], tt;
void dfs (int pos, int par) {
  in[pos] = ++tt; 
  for (auto j : adj[pos]) {
    if (j.first == par) continue;
    ett.push_back(j.second);
    dep[j.first] = 1 + dep[pos];
    dfs(j.first, pos);
  }
  out[pos] = tt;
}
void dfs2 (int pos) {
  for (auto j : adj[pos]) {
    if (in[j.first] < in[pos]) continue;
    ett2.push_back(j.second);
    dfs2(j.first);
  }
}
void find_pair (int n, vector <int> u, vector <int> v, int a, int b) {
  for (int i = 0; i + 1 < n; i++) {
    adj[u[i]].push_back({v[i], i});
    adj[v[i]].push_back({u[i], i});
  }
  vector <int> g(n - 1);
  ll U = ask(g);
  dfs(0, -1);
  for (int i = 0; i < n - 1; i++) {
    if (dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
  }
  int l = 0, r = n - 2, p1 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    g.clear(); g.resize(n - 1);
    for (auto &i : g) i = 0;
    for (int j = 0; j <= mid; j++) g[ett[j]] = 1;
    ll V = ask(g);
    if (V != U) {
      r = mid - 1; p1 = mid;
    } else {
      l = mid + 1;
    }
  }
  l = 0, r = n - 2; int p2 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    g.clear(); g.resize(n - 1);
    for (auto &i : g) i = 0;
    for (int j = mid; j + 1 < n; j++) g[ett[j]] = 1;
    ll V = ask(g);
    if (V != U) {
      l = mid + 1; p2 = mid;
    } else {
      r = mid - 1;
    }
  }
 // assert(p1 != -1); assert(p2 != -1);
  p1 = ett[p1]; p2 = ett[p2];
  if (in[v[p1]] <= in[v[p2]] && out[v[p2]] <= out[v[p1]]) {
    answer(u[p1], v[p2]);
    return;
  }
  dfs2(v[p1]);
  l = 0, r = (int)ett2.size() - 1; int ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    g.clear(); g.resize(n - 1);
    for (auto &i : g) i = 0;
    for (int i = mid; i < (int)ett2.size(); i++) {
      g[ett2[i]] = 1;
    }
    ll V = ask(g);
    if (V != U) {
      l = mid + 1; ans = mid;
    } else {
      r = mid - 1;
    }
  }
  assert(ans != -1);
  answer(v[ett2[ans]], v[p2]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3796 KB Output is correct
2 Correct 1 ms 3800 KB Output is correct
3 Correct 1 ms 3796 KB Output is correct
4 Correct 1 ms 3800 KB Output is correct
5 Correct 1 ms 3804 KB Output is correct
6 Correct 2 ms 4004 KB Output is correct
7 Correct 1 ms 3804 KB Output is correct
8 Correct 1 ms 3800 KB Output is correct
9 Correct 1 ms 3796 KB Output is correct
10 Correct 2 ms 4044 KB Output is correct
11 Correct 1 ms 3804 KB Output is correct
12 Correct 1 ms 3804 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3852 KB Output is correct
2 Correct 11 ms 4572 KB Output is correct
3 Correct 91 ms 9796 KB Output is correct
4 Correct 96 ms 9800 KB Output is correct
5 Correct 112 ms 9792 KB Output is correct
6 Correct 93 ms 9572 KB Output is correct
7 Correct 97 ms 9584 KB Output is correct
8 Correct 100 ms 9796 KB Output is correct
9 Correct 94 ms 9612 KB Output is correct
10 Correct 119 ms 9568 KB Output is correct
11 Correct 94 ms 11240 KB Output is correct
12 Correct 87 ms 11480 KB Output is correct
13 Correct 87 ms 11100 KB Output is correct
14 Correct 103 ms 10660 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5220 KB Output is correct
2 Correct 18 ms 6668 KB Output is correct
3 Correct 25 ms 8276 KB Output is correct
4 Correct 69 ms 16148 KB Output is correct
5 Correct 66 ms 16056 KB Output is correct
6 Correct 91 ms 16064 KB Output is correct
7 Correct 86 ms 16060 KB Output is correct
8 Correct 71 ms 16316 KB Output is correct
9 Correct 103 ms 16056 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3852 KB Output is correct
2 Correct 9 ms 4556 KB Output is correct
3 Correct 69 ms 8604 KB Output is correct
4 Correct 97 ms 10044 KB Output is correct
5 Correct 106 ms 10280 KB Output is correct
6 Correct 86 ms 9804 KB Output is correct
7 Correct 121 ms 10048 KB Output is correct
8 Correct 95 ms 10284 KB Output is correct
9 Correct 97 ms 9804 KB Output is correct
10 Correct 94 ms 10272 KB Output is correct
11 Correct 106 ms 10468 KB Output is correct
12 Correct 99 ms 12040 KB Output is correct
13 Correct 96 ms 11228 KB Output is correct
14 Correct 115 ms 11764 KB Output is correct
15 Correct 89 ms 9804 KB Output is correct
16 Correct 89 ms 9804 KB Output is correct
17 Correct 111 ms 11524 KB Output is correct
18 Correct 85 ms 10796 KB Output is correct
19 Correct 104 ms 9576 KB Output is correct
20 Correct 121 ms 12780 KB Output is correct
21 Runtime error 71 ms 20100 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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