#include "highway.h" #include <bits/stdc++.h> using namespace std; using ll = long long; void find_pair(int n, vector<int> u, vector<int> v, int a, int b) { int m = u.size(); vector<vector<pair<int, int>>> g(n); for (int i = 0; i < m; ++i) { g[u[i]].emplace_back(v[i], i); g[v[i]].emplace_back(u[i], i); } vector<int> w(m); ll dist = ask(w); int l = 0, r = m - 1; while (l < r) { int md = (l + r) >> 1; for (int i = 0; i < m; ++i) { w[i] = i <= md; } if (ask(w) != dist) { r = md; } else { l = md + 1; } } int id = l; vector<int> tr; vector<int> lc; vector<int> rc; vector<int> color(n); queue<int> q; color[u[id]] = 1; lc.push_back(u[id]); q.push(u[id]); color[v[id]] = 2; q.push(v[id]); rc.push_back(v[id]); tr.push_back(id); while (!q.empty()) { int u = q.front(); q.pop(); for (auto e : g[u]) { int v, id; tie(v, id) = e; if (!color[v]) { if (color[u] == 1) { color[v] = 1; lc.push_back(v); } else { color[v] = 2; rc.push_back(v); } tr.push_back(id); q.push(v); } } } assert(tr.size() == n - 1); auto get = [&](vector<int> comp) { int sz = comp.size(); int l = 0, r = sz - 1; while (l < r) { int md = (l + r) >> 1; vector<bool> was(n); for (int i = md + 1; i < sz; ++i) { was[comp[i]] = true; } for (int i = 0; i < m; ++i) { w[i] = was[u[i]] || was[v[i]]; } if (ask(w) != dist) { l = md + 1; } else { r = md; } } return comp[l]; }; answer(get(lc), get(rc)); } // g++ -std=c++14 grader.cpp highway.cpp

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from highway.cpp:3:
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:61:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    assert(tr.size() == n - 1);
           ~~~~~~~~~~^~~~~~~~