#include "highway.h"
#include <queue>
#include <algorithm>
struct Edge
{
Edge(int d, int i) : dest(d), id(i) {}
int dest, id;
bool operator ==(const Edge &other) const
{
return (dest == other.dest && id == other.id);
}
};
const int MAXN = 90000;
std::vector<Edge> graph[MAXN];
std::vector<int> trafficCondition;
std::queue<int> bfs;
std::vector<Edge> tree[MAXN];
int parent[MAXN], parentEdge[MAXN];
std::vector<int> opti;
inline void set0(int road)
{
trafficCondition[road] = 0;
}
inline void set1(int road)
{
trafficCondition[road] = 1;
}
inline void toogle(int road)
{
trafficCondition[road] = 1 - trafficCondition[road];
}
int findroot(int left, int right, long long expectedLength)
{
if (left == right)
return MAXN;
int middle = (left + right) / 2;
for (int iNode = 0; iNode <= middle; iNode++)
for (Edge &edge : graph[iNode])
set1(edge.id);
long long shortestPath = ask(trafficCondition);
for (int iNode = 0; iNode <= middle; iNode++)
for (Edge &edge : graph[iNode])
set0(edge.id);
if (shortestPath > expectedLength)
return std::min(middle, findroot(left, middle, expectedLength));
return findroot(middle + 1, right, expectedLength);
}
void buildtree(int root)
{
bfs.emplace(root);
parent[root] = -1;
std::fill_n(parentEdge, MAXN, -1);
parentEdge[root] = -2;
while (!bfs.empty())
{
int node = bfs.front();
bfs.pop();
for (Edge &edge : graph[node])
if (parentEdge[edge.dest] == -1)
{
tree[node].emplace_back(edge);
parent[edge.dest] = node;
parentEdge[edge.dest] = edge.id;
set1(edge.id);
bfs.emplace(edge.dest);
}
}
}
void toogledepth(int node, int depth, int maxDepth)
{
if (depth == maxDepth)
return;
for (Edge &edge : tree[node])
{
toogle(edge.id);
toogledepth(edge.dest, depth + 1, maxDepth);
}
}
void toogledepth2(int node, int depth, int maxDepth)
{
for (Edge &edge : tree[node])
{
if (depth >= maxDepth)
toogle(edge.id);
toogledepth2(edge.dest, depth + 1, maxDepth);
}
}
void makedepthset(int node, std::vector<int> &nodeSet, int depth, int maxDepth)
{
if (depth == maxDepth)
{
nodeSet.emplace_back(node);
return;
}
for (Edge &edge : tree[node])
makedepthset(edge.dest, nodeSet, depth + 1, maxDepth);
}
int searchextremity(std::vector<int> candidates, long long expectedLength, long long whenUpd)
{
if (candidates.size() == 1)
return candidates[0];
for (int iNode = 0; iNode < (int)candidates.size() / 2; iNode++)
set1(parentEdge[candidates[iNode]]);
long long shortestPath = ask(trafficCondition);
for (int iNode = 0; iNode < (int)candidates.size() / 2; iNode++)
set0(parentEdge[candidates[iNode]]);
if (shortestPath == expectedLength + whenUpd)
{
opti = std::vector<int>(candidates.begin() + candidates.size() / 2, candidates.end());
return searchextremity(std::vector<int>(candidates.begin(), candidates.begin() + candidates.size() / 2), expectedLength, -1);
}
if (shortestPath > expectedLength)
return searchextremity(std::vector<int>(candidates.begin(), candidates.begin() + candidates.size() / 2), expectedLength, whenUpd);
return searchextremity(std::vector<int>(candidates.begin() + candidates.size() / 2, candidates.end()), expectedLength, whenUpd);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
for (int iEdge = 0; iEdge < (int)U.size(); iEdge++)
{
graph[U[iEdge]].emplace_back(V[iEdge], iEdge);
graph[V[iEdge]].emplace_back(U[iEdge], iEdge);
}
trafficCondition.resize(U.size(), 0);
long long shortestPath = ask(trafficCondition);
long long edgesOnPath = shortestPath / (long long)A;
int root = findroot(0, N, shortestPath);
buildtree(root);
for (int i = 0; i < (int)U.size(); i++)
toogle(i);
toogledepth2(root, 0, edgesOnPath / 2);
long long newShort = ask(trafficCondition);
if (newShort == shortestPath)
{
std::vector<int> nodes;
makedepthset(root, nodes, 0, edgesOnPath / 2);
int s = searchextremity(nodes, shortestPath, B - A);
int t = searchextremity(opti, shortestPath, -1);
answer(s, t);
}
else
{
toogledepth2(root, 0, edgesOnPath / 2);
long long Tdepth = edgesOnPath / 2LL + (newShort - shortestPath) / (long long)(B - A);
toogledepth2(root, 0, Tdepth);
std::vector<int> nodes;
makedepthset(root, nodes, 0, Tdepth);
int t = searchextremity(nodes, shortestPath, -1);
int block = t;
while (parent[block] != -1)
{
tree[parent[block]].erase(std::find(tree[parent[block]].begin(), tree[parent[block]].end(), Edge(block, parentEdge[block])));
block = parent[block];
}
toogledepth2(root, 0, Tdepth);
toogledepth2(root, 0, edgesOnPath - Tdepth);
nodes.clear();
makedepthset(root, nodes, 0, edgesOnPath - Tdepth);
int s = searchextremity(nodes, shortestPath, -1);
answer(s, t);
}
}
