Submission #964860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964860	2024-04-17T16:44:08 Z	TAhmed33	Highway Tolls (IOI18_highway)	C++17	18 / 100	107 ms	16524 KB

highway

#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 (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 (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;
    }
  }
  p1 = ett[p1]; p2 = ett[p2];
  if (in[u[p1]] <= in[v[p2]] && out[v[p2]] <= out[u[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 (int i = mid; i < (int)ett2.size() - 1; i++) {
      g[ett2[i]] = 1;
    }
    ll V = ask(g);
    if (V != U) {
      l = mid + 1; ans = mid;
    } else {
      r = mid - 1;
    }
  }
  answer(v[ans], v[p2]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3852 KB	Output is correct
2	Correct	13 ms	4576 KB	Output is correct
3	Correct	83 ms	9680 KB	Output is correct
4	Correct	82 ms	9796 KB	Output is correct
5	Correct	95 ms	9588 KB	Output is correct
6	Correct	79 ms	9808 KB	Output is correct
7	Correct	93 ms	9812 KB	Output is correct
8	Correct	90 ms	9824 KB	Output is correct
9	Correct	92 ms	10280 KB	Output is correct
10	Correct	83 ms	9572 KB	Output is correct
11	Correct	92 ms	11156 KB	Output is correct
12	Correct	84 ms	11692 KB	Output is correct
13	Correct	90 ms	11128 KB	Output is correct
14	Correct	79 ms	10300 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	5288 KB	Output is correct
2	Correct	17 ms	6912 KB	Output is correct
3	Correct	25 ms	8048 KB	Output is correct
4	Correct	68 ms	16060 KB	Output is correct
5	Correct	75 ms	16524 KB	Output is correct
6	Correct	81 ms	16308 KB	Output is correct
7	Correct	107 ms	16268 KB	Output is correct
8	Correct	77 ms	16060 KB	Output is correct
9	Correct	94 ms	16056 KB	Output is correct