제출 #296218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296218		Bruteforceman	통행료 (IOI18_highway)	C++11	0 / 100	316 ms	19116 KiB

highway

#include "bits/stdc++.h"
#include "highway.h"
using namespace std;
const int maxn = 1e5;
vector <int> g[maxn];

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();
  int l, r;
  int initDist = ask(vector <int> (m, 0));
  l = 0, r = m;
  while(l < r) {
    vector <int> v (m, 0);
    int mid = (l + r + 1) >> 1;
    for(int i = 0; i < mid; i++) {
      v[i] = 1;
    }
    if(ask(v) == initDist) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  vector <int> state (m, 0);
  for(int i = 0; i < l; i++) state[i] = 1;
  vector <int> order;
  queue <int> Q;
  vector <int> dist (n, -1);
  Q.push(U[l]);
  Q.push(V[l]);
  dist[U[l]] = dist[V[l]] = 0;
  for(int i = 0; i < m; i++) {
    if(state[i] == 0) {
      g[U[i]].push_back(V[i]);
      g[V[i]].push_back(U[i]);
    }
  }
  while(not Q.empty()) {
    int x = Q.front();
    Q.pop();
    order.push_back(x);
    for(int i : g[x]) {
      if(dist[i] == -1) {
        dist[i] = dist[x] + 1;
        Q.push(i);
      }
    }
  }
  reverse(order.begin(), order.end());
  auto getEndpoint = [&] (vector <int> order) { 
    int l = 0, r = n - 1;
    while(l < r) {
      int mid = (l + r) >> 1;
      vector <int> v = state;
      vector <int> mark (n, 0);
      for(int i = 0; i <= mid; i++) {
        mark[order[i]] = 1;
      }
      for(int i = 0; i < m; i++) {
        if(mark[U[i]] || mark[V[i]]) {
          v[i] = 1;
        }
      }
      if(ask(v) == initDist) {
        l = mid + 1;
      } else {
        r = mid;
      }
    }
    return order[l];
  };
  int src = getEndpoint(order);
  Q.push(src);
  dist = vector <int> (n, -1);
  dist[src] = 0;
  order.clear();
  while(not Q.empty()) {
    int x = Q.front();
    Q.pop();
    order.push_back(x);
    for(int i : g[x]) {
      if(dist[i] == -1) {
        dist[i] = 1 + dist[x];
        Q.push(i);
      }
    }
  }
  reverse(order.begin(), order.end());
  int des = getEndpoint(order);
  answer(src, des);
}

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