제출 #1218658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218658		HappyCapybara	통행료 (IOI18_highway)	C++17	100 / 100	94 ms	11520 KiB

highway

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

#define ll long long

vector<vector<pair<int,int>>> g;

void dist(int s, vector<int>& d, vector<int>& es){
  d[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()){
    int cur = q.front();
    q.pop();
    for (pair<int,int> next : g[cur]){
      if (d[next.first] == -1){
        d[next.first] = d[cur]+1;
        es.push_back(next.second);
        q.push(next.first);
      }
    }
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
  int M = U.size();
  g.resize(N);
  for (int i=0; i<M; i++){
    g[U[i]].push_back({V[i], i});
    g[V[i]].push_back({U[i], i});
  }
  ll len = ask(vector<int>(M, 0))/A;
  int l = 0, r = M;
  while (l < r-1){
    int m = (l+r)/2;
    vector<int> w(M, 0);
    for (int i=0; i<m; i++) w[i] = 1;
    if (ask(w) > (ll)A*len) r = m;
    else l = m;
  }
  int e = l, u = U[e], v = V[e];
  //cout << e << endl;
  vector<int> du(N, -1), dv(N, -1), deu, dev, eu, ev;
  dist(u, du, deu);
  dist(v, dv, dev);
  for (int x : deu){
    if (du[U[x]] < dv[U[x]] && du[V[x]] < dv[V[x]]) eu.push_back(x);
  }
  reverse(eu.begin(), eu.end());
  eu.push_back(e);
  for (int x : dev){
    if (dv[U[x]] < du[U[x]] && dv[V[x]] < du[V[x]]) ev.push_back(x);
  }
  reverse(ev.begin(), ev.end());
  ev.push_back(e);
  /*for (int x : eu) cout << x << " ";
  cout << endl;
  for (int x : ev) cout << x << " ";
  cout << endl;*/
  l = 0; r = eu.size();
  while (l < r-1){
    int m = (l+r)/2;
    vector<int> w(M, 1);
    for (int x : ev) w[x] = 0;
    for (int i=m; i<eu.size(); i++) w[eu[i]] = 0;
    if (ask(w) > (ll)A*len) r = m;
    else l = m;
  }
  int s = U[eu[l]];
  if (dv[V[eu[l]]] > dv[U[eu[l]]]) s = V[eu[l]];
  l = 0; r = ev.size();
  while (l < r-1){
    int m = (l+r)/2;
    vector<int> w(M, 1);
    for (int x : eu) w[x] = 0;
    for (int i=m; i<ev.size(); i++) w[ev[i]] = 0;
    if (ask(w) > (ll)A*len) r = m;
    else l = m;
  }
  int t = U[ev[l]];
  if (du[V[ev[l]]] > du[U[ev[l]]]) t = V[ev[l]];
  answer(s, t);
}

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