Submission #964850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964850	2024-04-17T16:27:59 Z	TAhmed33	Highway Tolls (IOI18_highway)	C++17	18 / 100	124 ms	16300 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;
  }
  U /= a; 
  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	3796 KB	Output is correct
3	Correct	1 ms	3928 KB	Output is correct
4	Correct	1 ms	3800 KB	Output is correct
5	Correct	3 ms	3800 KB	Output is correct
6	Correct	2 ms	3804 KB	Output is correct
7	Correct	1 ms	3808 KB	Output is correct
8	Correct	1 ms	3796 KB	Output is correct
9	Correct	1 ms	4048 KB	Output is correct
10	Correct	1 ms	3796 KB	Output is correct
11	Correct	1 ms	3796 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	3852 KB	Output is correct
2	Correct	10 ms	4572 KB	Output is correct
3	Correct	112 ms	9572 KB	Output is correct
4	Correct	99 ms	9788 KB	Output is correct
5	Correct	80 ms	9796 KB	Output is correct
6	Correct	107 ms	9800 KB	Output is correct
7	Correct	92 ms	9596 KB	Output is correct
8	Correct	83 ms	9804 KB	Output is correct
9	Correct	84 ms	9804 KB	Output is correct
10	Correct	124 ms	9572 KB	Output is correct
11	Correct	96 ms	10960 KB	Output is correct
12	Correct	92 ms	11664 KB	Output is correct
13	Correct	122 ms	11356 KB	Output is correct
14	Correct	85 ms	10428 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	5232 KB	Output is correct
2	Correct	21 ms	6672 KB	Output is correct
3	Correct	22 ms	8300 KB	Output is correct
4	Correct	80 ms	16160 KB	Output is correct
5	Correct	81 ms	16076 KB	Output is correct
6	Correct	69 ms	16060 KB	Output is correct
7	Correct	72 ms	16300 KB	Output is correct
8	Correct	70 ms	16060 KB	Output is correct
9	Correct	76 ms	16076 KB	Output is correct