제출 #1036468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036468		abczz	통행료 (IOI18_highway)	C++17	0 / 100	12 ms	3740 KiB

highway

#include "highway.h"
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#define ll long long

using namespace std;

ll l, r, mid, a, b, s, q, rt, P[90000], E[90000];
bool visited[90000];
vector <ll> X;
vector <array<ll, 2> > adj[90000];
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  ll M = U.size();
  queue <ll> Q;
  for (int i=0; i<M; ++i) {
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  vector <int> W(M), Z(M);
  for (int i=0; i<M; ++i) W[i] = 0, Z[i] = 1;
  s = ask(W);
  l = 0, r = N-1;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = 0;
    for (int i=0; i<=mid; ++i) {
      for (auto [u, x] : adj[i]) W[x] = 1;
    }
    q = ask(W);
    if (q > s) r = mid;
    else l = mid+1;
  }
  rt = l;
  Q.push(rt);
  visited[rt] = 1;
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    X.push_back(u);
    for (auto [v, x] : adj[u]) {
      if (!visited[v] && v >= rt) {
        Z[x] = 0, visited[v] = 1, E[v] = x, P[v] = u;
        Q.push(v);
      }
    }
  }
  reverse(X.begin(), X.end());
  X.pop_back();
  l = 0, r = X.size()-1;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = Z[i];
    for (int i=mid; i>=0; --i) {
      if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
    }
    q = ask(W);
    if (q > s) r = mid;
    else l = mid+1;
  }
  a = l;
  l = a+1, r = X.size();
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<M; ++i) W[i] = Z[i];
    for (int i=mid; i>=0; --i) {
      if (!W[E[P[X[i]]]]) W[E[X[i]]] = 1;
    }
    q = ask(W);
    if (q > s+B-A) r = mid;
    else l = mid+1;
  }
  if (l == (ll)X.size()) answer(rt, X[a]);
  else answer(X[a], X[l]);
}

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