Submission #1221959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221959		madamadam3	Highway Tolls (IOI18_highway)	C++20	51 / 100	268 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

using vi = vector<int>;
using vvi = vector<vi>;

int n, m, a, b;

vvi adj;
vi dist, eu, ev, par, epar, depth, score;

void dfs(int u, int p) {
  if (u != p) dist[u] = dist[p] + 1;

  for (int v : adj[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
}

int score_nodes(int u, int p) {
  if (u == p) depth[u] = 0;
  else depth[u] = depth[p] + 1;

  int max_child = depth[u];
  for (int v : adj[u]) {
    if (v == p) continue;
    max_child = max(max_child, score_nodes(v, u));
  }

  score[u] = max_child - depth[u];
  return max_child;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  n = N; m = U.size(); eu = U; ev = V;
  adj.assign(n, vi()); for (int i = 0; i < m; i++) adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]);
  dist.assign(n, 0);
  dfs(0, 0);
  score.assign(n, 0); depth.assign(n, 0);
  score_nodes(0, 0);
  par.assign(n, -1); epar.assign(n, -1); for (int i = 0; i < m; i++) {
    if (dist[U[i]] < dist[V[i]]) {
      par[V[i]] = U[i];
      epar[V[i]] = i;
    } else {
      par[U[i]] = V[i];
      epar[U[i]] = i;
    }
  }

  ll base = ask(vi(m, 0));
  int path_length = base / ll(A);

  // cout << "Base: " << base << " Path length: " << path_length << "\n";

  vi by_score(n); iota(by_score.begin(), by_score.end(), 0);
  sort(by_score.begin(), by_score.end(), [&](int a, int b) {return score[a] < score[b];});
  
  int lo = 0, hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    vi qn(m, 0); for (int i = 0; i <= mid; i++) qn[epar[by_score[i]]] = 1;

    ll ans = ask(qn);
    if (ans == base) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }

  int S = by_score[lo];
  dist.assign(n, 0);
  dfs(S, S);
  par.assign(n, -1); epar.assign(n, -1); for (int i = 0; i < m; i++) {
    if (dist[U[i]] < dist[V[i]]) {
      par[V[i]] = U[i];
      epar[V[i]] = i;
    } else {
      par[U[i]] = V[i];
      epar[U[i]] = i;
    }
  }
  
  vi options; for (int i = 0; i < n; i++) if (dist[i] == path_length) options.push_back(i);

  lo = 0; hi = options.size();
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    vi qn(m, 0); for (int i = lo; i <= mid; i++) qn[epar[options[i]]] = 1;

    ll ans = ask(qn);
    if (ans == base) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }

  // answer(0, options[lo]);
  int T = options[lo];
  // cout << "S: " << S << " T: " << T << "\n";
  answer(S, T);
  // answer(0, 0);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31