제출 #1164132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164132		iah	통행료 (IOI18_highway)	C++20	0 / 100	8 ms	3368 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);

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

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

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

      REP(i, mid + 1) {
        int j = vers[i];

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

        for (auto x: adj[j]) {
          if (type[x.fi] != cur) {
            continue;
          }

          if ((type[x.fi] == 0 && du[x.fi] < du[j]) || (type[x.fi] == 1 && dv[x.fi] < dv[j])) {
            w[x.se] = 1;
//           cout << "change " << x.se << "\n";
          }
        }
      }

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

    if (pos == sz(vers)) {
      pos = 0;
    }

//    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