#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 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);
toogledepth(root, 0, edgesOnPath / 2);
long long newShort = ask(trafficCondition);
toogledepth(root, 0, edgesOnPath / 2);
if (newShort == edgesOnPath * (long long)B)
{
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
{
long long Sdepth = (newShort - shortestPath - (edgesOnPath / 2LL) * (long long)(B - A)) / (long long)(B - A);
std::vector<int> nodes;
makedepthset(root, nodes, 0, edgesOnPath - Sdepth);
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];
}
nodes.clear();
makedepthset(root, nodes, 0, Sdepth);
int s = searchextremity(nodes, shortestPath, -1);
answer(s, t);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4856 KB |
Output is correct |
2 |
Correct |
6 ms |
4856 KB |
Output is correct |
3 |
Correct |
6 ms |
4884 KB |
Output is correct |
4 |
Correct |
6 ms |
4856 KB |
Output is correct |
5 |
Correct |
7 ms |
4856 KB |
Output is correct |
6 |
Correct |
6 ms |
4796 KB |
Output is correct |
7 |
Correct |
6 ms |
4856 KB |
Output is correct |
8 |
Correct |
7 ms |
4856 KB |
Output is correct |
9 |
Correct |
6 ms |
4856 KB |
Output is correct |
10 |
Correct |
7 ms |
4856 KB |
Output is correct |
11 |
Correct |
6 ms |
4796 KB |
Output is correct |
12 |
Correct |
7 ms |
4856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4928 KB |
Output is correct |
2 |
Correct |
26 ms |
5752 KB |
Output is correct |
3 |
Correct |
208 ms |
12120 KB |
Output is correct |
4 |
Correct |
201 ms |
12184 KB |
Output is correct |
5 |
Correct |
228 ms |
12240 KB |
Output is correct |
6 |
Correct |
225 ms |
12032 KB |
Output is correct |
7 |
Correct |
217 ms |
12168 KB |
Output is correct |
8 |
Correct |
223 ms |
12168 KB |
Output is correct |
9 |
Correct |
212 ms |
12028 KB |
Output is correct |
10 |
Correct |
216 ms |
12168 KB |
Output is correct |
11 |
Correct |
220 ms |
12852 KB |
Output is correct |
12 |
Correct |
222 ms |
13304 KB |
Output is correct |
13 |
Correct |
207 ms |
13152 KB |
Output is correct |
14 |
Correct |
230 ms |
13408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
5752 KB |
Output is correct |
2 |
Correct |
44 ms |
6704 KB |
Output is correct |
3 |
Correct |
68 ms |
7492 KB |
Output is correct |
4 |
Correct |
186 ms |
13596 KB |
Output is correct |
5 |
Correct |
177 ms |
12668 KB |
Output is correct |
6 |
Correct |
180 ms |
16164 KB |
Output is correct |
7 |
Correct |
201 ms |
12712 KB |
Output is correct |
8 |
Correct |
173 ms |
14624 KB |
Output is correct |
9 |
Correct |
184 ms |
12756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
4856 KB |
Output is correct |
2 |
Correct |
28 ms |
5628 KB |
Output is correct |
3 |
Correct |
198 ms |
10492 KB |
Output is correct |
4 |
Correct |
285 ms |
12104 KB |
Output is correct |
5 |
Correct |
209 ms |
11964 KB |
Output is correct |
6 |
Correct |
228 ms |
12056 KB |
Output is correct |
7 |
Correct |
221 ms |
11964 KB |
Output is correct |
8 |
Correct |
229 ms |
12000 KB |
Output is correct |
9 |
Correct |
224 ms |
12172 KB |
Output is correct |
10 |
Correct |
221 ms |
12120 KB |
Output is correct |
11 |
Correct |
224 ms |
13200 KB |
Output is correct |
12 |
Correct |
247 ms |
13356 KB |
Output is correct |
13 |
Correct |
230 ms |
13156 KB |
Output is correct |
14 |
Correct |
224 ms |
13168 KB |
Output is correct |
15 |
Correct |
230 ms |
11956 KB |
Output is correct |
16 |
Correct |
256 ms |
11948 KB |
Output is correct |
17 |
Correct |
225 ms |
12992 KB |
Output is correct |
18 |
Correct |
224 ms |
13300 KB |
Output is correct |
19 |
Correct |
208 ms |
11948 KB |
Output is correct |
20 |
Correct |
216 ms |
12768 KB |
Output is correct |
21 |
Correct |
231 ms |
12688 KB |
Output is correct |
22 |
Correct |
255 ms |
12556 KB |
Output is correct |
23 |
Correct |
223 ms |
11852 KB |
Output is correct |
24 |
Correct |
231 ms |
12580 KB |
Output is correct |
25 |
Correct |
282 ms |
17292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
5648 KB |
Output is incorrect: {s, t} is wrong |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
5752 KB |
Output is incorrect: more than 100 calls to ask |
2 |
Halted |
0 ms |
0 KB |
- |