Submission #964874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964874	2024-04-17T16:49:47 Z	TAhmed33	Highway Tolls (IOI18_highway)	C++17	18 / 100	118 ms	16308 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(); 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	3800 KB	Output is correct
3	Correct	2 ms	3796 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	3796 KB	Output is correct
8	Correct	1 ms	3796 KB	Output is correct
9	Correct	1 ms	3928 KB	Output is correct
10	Correct	2 ms	3928 KB	Output is correct
11	Correct	1 ms	3800 KB	Output is correct
12	Correct	1 ms	3792 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	80 ms	9584 KB	Output is correct
4	Correct	97 ms	9796 KB	Output is correct
5	Correct	69 ms	9588 KB	Output is correct
6	Correct	98 ms	9576 KB	Output is correct
7	Correct	118 ms	10000 KB	Output is correct
8	Correct	108 ms	9572 KB	Output is correct
9	Correct	77 ms	9808 KB	Output is correct
10	Correct	107 ms	9568 KB	Output is correct
11	Correct	84 ms	11184 KB	Output is correct
12	Correct	105 ms	11456 KB	Output is correct
13	Correct	79 ms	11124 KB	Output is correct
14	Correct	117 ms	10280 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5288 KB	Output is correct
2	Correct	24 ms	6648 KB	Output is correct
3	Correct	26 ms	8040 KB	Output is correct
4	Correct	72 ms	16308 KB	Output is correct
5	Correct	80 ms	16304 KB	Output is correct
6	Correct	61 ms	16116 KB	Output is correct
7	Correct	71 ms	16156 KB	Output is correct
8	Correct	68 ms	16084 KB	Output is correct
9	Correct	71 ms	16064 KB	Output is correct