Submission #1221941

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

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

  // for (int j = 0; j < 50; ++j) {
    // vector<int> w(M);
    // for (int i = 0; i < M; ++i) {
    //   w[i] = 0;
    // }
    // ll toll = ask(w);
  // }

  answer(0, options[lo]);
}

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