#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
array<int, 5> seeds = {409887653, 59456231, 56246231, 56246233, 931621953};
mt19937 rng((seeds[std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()^3)%seeds.size()]);
int get_rand(int l, int r){
return uniform_int_distribution<int>(l, r)(rng);
}
int A, B, C, M, n;
ll initial;
int path_len;
int ed;
vector<vector<pair<int, int> > > g;
map<pair<int, int>, int> deco;
vector<char> state;
vector<int> gord;
bool rec(int u, int p, int pared){
assert(state[u] == 0);
state[u] = 1;
int pool = -1;
auto add_cand = [&](int e){
if(pool == -1){
pool = e;
} else {
gord.push_back(pool);
gord.push_back(e);
pool = -1;
}
};
for(auto const&e:g[u]){
if(e.first == p) continue;
if(state[e.first] == 0){
bool did = rec(e.first, u, e.second);
if(!did){
add_cand(e.second);
}
} else if(state[e.first] == 1){
add_cand(e.second);
}
}
state[u] = 2;
if(pool != -1){
gord.push_back(pool);
gord.push_back(pared);
return true;
}
return false;
}
vector<int> line_graph_allign(){
state.assign(n, 0);
gord.clear();
rec(get_rand(0, n-1), -1, -1);
if(M%2){
assert(gord.back() == -1);
gord.pop_back();
gord.push_back(gord.back());
}
return gord;
}
int find_vertex(int M, vector<int> const&U, vector<int> const&V){
vector<int> ord = line_graph_allign();
for(int i=0;i<ord.size();i+=2){
int j = 2*get_rand(0, i/2);
swap(ord[i], ord[i-j]);
swap(ord[i+1], ord[i-j+1]);
}
/*for(int i=0;i<ord.size();i+=2){
cerr << U[ord[i]] << " " << V[i] << " | " << U[i+1] << " " << V[i+1] << "\n";
}*/
int l = -1, r = (M+1)/2-1;
while(l+1 < r){
int m = l + (r-l)/2;
vector<int> v(M, 1);
for(int i=0;i/2<=m;++i) v[ord[i]] = 0;
ll mid = ask(v);
if(mid == path_len*(ll)A){
r = m;
} else {
l = m;
}
}
map<int, int> cnt;
for(auto const&e:{U, V}){
for(auto const&i:{ord[2*r], ord[2*r+1]}){
++cnt[e[i]];
}
}
for(auto const&e:cnt){
if(e.second == 2){
return e.first;
}
}
assert(0);
return -1;
}
int far_search(int u, vector<int> const&U, vector<int> const&V, bool fix_d){
vector<int> ord, vis(n, 0);
vector<int> inv_ord(n);
vector<int> d;
ord.push_back(u);
d.push_back(0);
vis[u] = 1;
for(int i=0;i<(int)ord.size();++i){
int v = ord[i];
inv_ord[v] = i;
for(auto const&f:g[v]){
auto const e = f.first;
if(!vis[e]){
vis[e] = 1;
ord.push_back(e);
d.push_back(d[i]+1);
}
}
}
assert((int)ord.size() == n);
int l = 0, r = n;
if(fix_d){
l = lower_bound(d.begin(), d.end(), path_len) - d.begin();
r = upper_bound(d.begin(), d.end(), path_len) - d.begin();
}
while(l+1 < r){
int m = l + (r-l)/2;
vector<int> v(M, 1);
for(int i=0;i<M;++i){
if(inv_ord[U[i]] < m && inv_ord[V[i]] < m){
v[i] = 0;
}
}
ll dist = ask(v);
if(dist == path_len * (ll) A){
r = m;
} else {
l = m;
}
}
return ord[l];
}
void find_pair(int N, vector<int> U, vector<int> V, int A_, int B_) {
n=N; A=A_; B=B_;
C = B-A;
M = U.size();
for(int i=0;i<M;++i){
deco[make_pair(U[i], V[i])] = i;
deco[make_pair(V[i], U[i])] = i;
}
initial = ask(vector<int>(M, 1));
assert(initial % B == 0);
path_len = initial / B;
//if(path_len <= 2) ask(vector<int>(M, 1));
g.assign(N, vector<pair<int, int> >());
for(int i=0;i<M;++i){
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
for(auto &e:g) shuffle(e.begin(), e.end(), rng);
int start = find_vertex(M, U, V);
//cerr << "ed " << ed << " : " << U[ed] << " " << V[ed] << "\n";
const int S = far_search(start, U, V, false);
const int T = far_search(S, U, V, true);
answer(S, T);
}
Compilation message
highway.cpp:11:143: error: expected ']' before ')' token
mt19937 rng((seeds[std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()^3)%seeds.size()]);
^
highway.cpp:11:157: error: expected ')' before ']' token
mt19937 rng((seeds[std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()^3)%seeds.size()]);
^
highway.cpp: In function 'int find_vertex(int, const std::vector<int>&, const std::vector<int>&)':
highway.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ord.size();i+=2){
~^~~~~~~~~~~
