Submission #964869

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964869	2024-04-17T16:48:23 Z	TAhmed33	Highway Tolls (IOI18_highway)	C++17	18 / 100	131 ms	16360 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 (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;
    }
  }
  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() - 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	1 ms	3800 KB	Output is correct
2	Correct	1 ms	3792 KB	Output is correct
3	Correct	2 ms	3800 KB	Output is correct
4	Correct	1 ms	3796 KB	Output is correct
5	Correct	1 ms	3800 KB	Output is correct
6	Correct	1 ms	3800 KB	Output is correct
7	Correct	1 ms	3804 KB	Output is correct
8	Correct	1 ms	3804 KB	Output is correct
9	Correct	1 ms	3804 KB	Output is correct
10	Correct	1 ms	3804 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	2 ms	3848 KB	Output is correct
2	Correct	12 ms	4576 KB	Output is correct
3	Correct	102 ms	9608 KB	Output is correct
4	Correct	105 ms	10028 KB	Output is correct
5	Correct	115 ms	9796 KB	Output is correct
6	Correct	90 ms	9592 KB	Output is correct
7	Correct	131 ms	9808 KB	Output is correct
8	Correct	83 ms	9804 KB	Output is correct
9	Correct	86 ms	9796 KB	Output is correct
10	Correct	87 ms	9812 KB	Output is correct
11	Correct	98 ms	10972 KB	Output is correct
12	Correct	87 ms	11708 KB	Output is correct
13	Correct	102 ms	11108 KB	Output is correct
14	Correct	99 ms	10276 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	5292 KB	Output is correct
2	Correct	24 ms	6920 KB	Output is correct
3	Correct	29 ms	8200 KB	Output is correct
4	Correct	66 ms	16360 KB	Output is correct
5	Correct	70 ms	16072 KB	Output is correct
6	Correct	79 ms	16060 KB	Output is correct
7	Correct	68 ms	16056 KB	Output is correct
8	Correct	87 ms	16308 KB	Output is correct
9	Correct	67 ms	16064 KB	Output is correct