제출 #605299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605299		piOOE	Highway Tolls (IOI18_highway)	C++17	컴파일 에러	0 ms	0 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

using ll = long long;

#define int ll

void find_pair(int n, vector<int> A, vector<int> B, int a, int b) {
  int m = (int) B.size();

  const ll val = ask(vector<int32_t>(m));

  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; ++i) {
    g[A[i]].push_back({B[i], i});
    g[B[i]].push_back({A[i], i});
  }

  set<int> useless;

  function<int(vector<int>)> bin_search = [&](const vector<int> &v) -> int {
    if (v.size() == 1) {
      return v[0];
    }
    int sz = (int) v.size();
    assert(sz > 0);
    int mid = int(v.size() >> 1);
    vector<int> L(mid), R(sz - mid);
    for (int i = 0; i < mid; ++i) {
      L[i] = v[i];
    }
    for (int i = mid; i < sz; ++i) {
      R[i - mid] = v[i];
    }
    vector<int32_t> nxt(m, 0);
    for (int x: R) {
      for (auto [to, i]: g[x]) {
        nxt[i] = 1;
      }
    }
    ll now = ask(nxt);
    if (now == val) {
      for (int x: R) {
        useless.insert(x);
      }
      return bin_search(L);
    } else {
      return bin_search(R);
    }
  };

  auto solve = [&](int s) {
    //solves for tree with known S
    int len = val / a;
    vector<int> depth(n, -1);
    depth[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto [to, i]: g[v]) {
        if (depth[to] == -1) {
          depth[to] = depth[v] + 1;
          q.push(to);
        }
      }
    }
    vector<int> canditates;
    for (int i = 0; i < n; ++i) {
      if (depth[i] == len && !useless.count(i)) {
        canditates.push_back(i);
      }
    }
    answer(s, bin_search(canditates));
  };

  vector<int> u(n);
  iota(u.begin(), u.end(), 0);

  int mid = bin_search(u);

  vector<int> depth(n, -1);
  depth[mid] = 0;
  queue<int> q;
  q.push(mid);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto [to, i]: g[v]) {
      if (depth[to] == -1) {
        depth[to] = depth[v] + 1;
        q.push(to);
      }
    }
  }
  sort(u.begin(), u.end(), [&depth](int i, int j) {
    return depth[i] < depth[j];
  });
  u.erase(u.begin(), stable_partition(u.begin(), u.end(), [&useless](int i) {
    return useless.count(i);
  }));
  solve(bin_search(u));
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccY9HLFo.o: in function `main':
grader.cpp:(.text.startup+0x16c): undefined reference to `find_pair(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, int, int)'
collect2: error: ld returned 1 exit status