Submission #1221943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221943		madamadam3	Highway Tolls (IOI18_highway)	C++20	6 / 100	281 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;

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);
  }
}

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);
  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);
  
  int lo = 1, hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    vi qn(m, 0); for (int i = 1; i <= mid; i++) qn[epar[i]] = 1;

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

  int S = par[lo];
  int T = par[lo] + path_length;

  // vi options; for (int i = 1; i < n; i++) if (dist[i] == path_length) options.push_back(i);

  // int 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]);
  answer(S, T);
}

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