Submission #1164146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164146		iah	Highway Tolls (IOI18_highway)	C++20	0 / 100	126 ms	9016 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

#define NAME ""
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

const int nmax = 9e4;
vector < pii > adj[nmax + 4];

void find_pair(int n, std::vector<int> u, std::vector<int> v, int costa, int costb) {
  int m = sz(u);

  REP(i, m) {
    adj[u[i]].push_back({v[i], i});
    adj[v[i]].push_back({u[i], i});
  }

  vector < int > w(m, 0);

  ll dist = ask(w);

  int l = 0, r = m - 1, pos = 0;

  while (l <= r) {
    int mid = (l + r) >> 1;

    REP(i, mid + 1) {
      w[i] = 1;
    }

//    cout << ask(w) << " " << dist << " " << mid << "\n";

    if (ask(w) != dist) {
      pos = mid;
      r = mid - 1;
    }
    else {
      l = mid + 1;
    }

    REP(i, mid + 1) {
      w[i] = 0;
    }
  }

//  cout << pos << "\n";

//  REP(i, pos) {
//    w[i] = 1;
//  }

  auto bfs = [&] (const int &i) {
    vector < int > d(n, -1);
    d[i] = 0;
    deque < int > dq;
    int timer = 0;
    dq.push_back(i);

    while (!dq.empty()) {
      int i = dq.front();
      dq.pop_front();

      for (auto x: adj[i]) {
        if (w[x.se] == 1) {
          if (d[x.fi] == -1 || d[x.fi] > d[i] + costb) {
            d[x.fi] = d[i] + costb;
            dq.push_back(x.fi);
          }
        }
        else {
          if (d[x.fi] == -1 || d[x.fi] > d[i] + costa) {
            d[x.fi] = d[i] + costa;
            dq.push_front(x.fi);
          }
        }
      }
    }

    return move(d);
  };

  vector < int > du = bfs(u[pos]);
  vector < int > dv = bfs(v[pos]);

  vector < int > veru, verv, type(n, -1);

  REP(i, n) {
    if (du[i] < dv[i]) {
      veru.push_back(i);
      type[i] = 0;
    }
    else if (du[i] > dv[i]) {
      verv.push_back(i);
      type[i] = 1;
    }
  }

//  for (auto x: veru) {
//    cout << x << " ";
//  }
//  cout << "\n";
//  for (auto x: verv) {
//    cout << x << " ";
//  }
//  cout << "\n";

  auto solve = [&] (const int &cur, const vector < int > & vers) {
    int l = 0, r = sz(vers) - 1, pos = 0;

    while (l <= r) {
      int mid = (l + r) >> 1;
      vector < int > w(m, 0);

      FOR(i, mid + 1, sz(vers) - 1) {
        int j = vers[i];

//        cout << j << " " << type[j] << "\n";

        for (auto x: adj[j]) {
          w[x.se] = 1;
        }
      }

      if (ask(w) == dist) {
        pos = mid;
        r = mid - 1;
      }
      else {
        l = mid + 1;
      }
    }

//    for (auto x: vers) {
//      cout << x << " ";
//    }
//    cout << "-> " << vers[pos] << "\n";

    return vers[pos];
  };

  answer(solve(0, veru), solve(1, verv));
}

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