Submission #964882

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964882	2024-04-17T16:54:59 Z	TAhmed33	Highway Tolls (IOI18_highway)	C++17	18 / 100	121 ms	16316 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;
    }
  }
 // 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(u[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	3800 KB	Output is correct
2	Correct	1 ms	3796 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	3800 KB	Output is correct
6	Correct	1 ms	3800 KB	Output is correct
7	Correct	1 ms	3800 KB	Output is correct
8	Correct	1 ms	3796 KB	Output is correct
9	Correct	1 ms	3796 KB	Output is correct
10	Correct	1 ms	3800 KB	Output is correct
11	Correct	1 ms	3796 KB	Output is correct
12	Correct	2 ms	3928 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	9 ms	4572 KB	Output is correct
3	Correct	76 ms	9572 KB	Output is correct
4	Correct	106 ms	10036 KB	Output is correct
5	Correct	72 ms	9588 KB	Output is correct
6	Correct	77 ms	9596 KB	Output is correct
7	Correct	121 ms	9804 KB	Output is correct
8	Correct	87 ms	9576 KB	Output is correct
9	Correct	83 ms	10040 KB	Output is correct
10	Correct	72 ms	9736 KB	Output is correct
11	Correct	107 ms	11440 KB	Output is correct
12	Correct	99 ms	11464 KB	Output is correct
13	Correct	85 ms	11044 KB	Output is correct
14	Correct	93 ms	10416 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5292 KB	Output is correct
2	Correct	28 ms	6844 KB	Output is correct
3	Correct	39 ms	8052 KB	Output is correct
4	Correct	120 ms	16316 KB	Output is correct
5	Correct	70 ms	16064 KB	Output is correct
6	Correct	77 ms	16272 KB	Output is correct
7	Correct	107 ms	16068 KB	Output is correct
8	Correct	72 ms	16272 KB	Output is correct
9	Correct	65 ms	16308 KB	Output is correct