제출 #1057301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057301		TAhmed33	통행료 (IOI18_highway)	C++17	100 / 100	195 ms	43844 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
int n, m;
map <int, int> ind[MAXN];
vector <int> cc[MAXN];
int dist[MAXN]; 
int in[MAXN], out[MAXN], tt, p[MAXN];
int gg[MAXN];
void dfs (int pos) {
  in[pos] = ++tt; gg[tt] = pos;
  for (auto j : cc[pos]) {
    p[j] = pos;
    dfs(j);
  }
  out[pos] = tt;
}
void find_pair (int N, vector <int> U, vector <int> V, int A, int B) {
  n = N; m = U.size();
  vector <int> x(m, 0);
  ll z = ask(x);
  for (int i = 0; i < m; i++) {
    adj[U[i]].push_back(V[i]);
    adj[V[i]].push_back(U[i]);
    ind[U[i]][V[i]] = ind[V[i]][U[i]] = i;
  }
  int l = 0, r = m - 1, ans = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    x.assign(m, 0);
    for (int j = 0; j < mid; j++) {
      x[j] = 1;
    }
    if (ask(x) == z) {
      l = mid + 1; ans = mid;
    } else {
      r = mid - 1;
    }
  }
  memset(dist, -1, sizeof(dist));
  queue <int> cur;
  cur.push(U[ans]); cur.push(V[ans]); dist[V[ans]] = 1; dist[U[ans]] = 0;
  cc[U[ans]].push_back(V[ans]);
  vector <int> spec = {ans};
  while (!cur.empty()) {
    auto k = cur.front();
    cur.pop();
    for (auto j : adj[k]) {
      if (dist[j] == -1) {
        dist[j] = dist[k] + 1;
        cc[k].push_back(j);
        cur.push(j); 
        spec.push_back(ind[j][k]);
      }
    }
  }
  x.assign(m, 1);
  p[U[ans]] = -1;
  swap(cc[U[ans]].front(), cc[U[ans]].back());
  dfs(U[ans]);
  l = 2, r = in[V[ans]] - 1; int ans2 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    for (auto i : spec) {
      x[i] = 0;
    }
    for (int j = mid; j <= in[V[ans]] - 1; j++) {
      x[ind[gg[j]][p[gg[j]]]] = 1;
    }
    if (ask(x) != z) {
      l = mid + 1; ans2 = mid;
    } else {
      r = mid - 1;
    }
  }
  if (ans2 == -1) {
    ans2 = U[ans];
  } else {
    ans2 = gg[ans2];
  }
  l = in[V[ans]], r = n; int ans3 = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    for (auto i : spec) {
      x[i] = 0;
    }
    for (int j = mid; j <= n; j++) {
      x[ind[gg[j]][p[gg[j]]]] = 1;
    }
    if (ask(x) != z) {
      l = mid + 1; ans3 = mid;
    } else {
      r = mid - 1;
    }
  }
  assert(ans3 != -1);
  ans3 = gg[ans3];
  answer(ans2, ans3);
}

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