#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 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])
toogle(edge.id);
long long shortestPath = ask(trafficCondition);
for (int iNode = 0; iNode <= middle; iNode++)
for (Edge &edge : graph[iNode])
toogle(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;
toogle(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++)
toogle(parentEdge[candidates[iNode]]);
long long shortestPath = ask(trafficCondition);
for (int iNode = 0; iNode < (int)candidates.size() / 2; iNode++)
toogle(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);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4776 KB |
Output is correct |
2 |
Correct |
6 ms |
4856 KB |
Output is correct |
3 |
Correct |
6 ms |
4856 KB |
Output is correct |
4 |
Correct |
6 ms |
4856 KB |
Output is correct |
5 |
Correct |
6 ms |
4776 KB |
Output is correct |
6 |
Correct |
6 ms |
4856 KB |
Output is correct |
7 |
Runtime error |
12 ms |
9592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4928 KB |
Output is correct |
2 |
Correct |
25 ms |
5624 KB |
Output is correct |
3 |
Correct |
227 ms |
12216 KB |
Output is correct |
4 |
Correct |
223 ms |
12140 KB |
Output is correct |
5 |
Correct |
224 ms |
12176 KB |
Output is correct |
6 |
Correct |
216 ms |
12036 KB |
Output is correct |
7 |
Correct |
214 ms |
12108 KB |
Output is correct |
8 |
Correct |
219 ms |
12404 KB |
Output is correct |
9 |
Correct |
210 ms |
12032 KB |
Output is correct |
10 |
Correct |
218 ms |
12112 KB |
Output is correct |
11 |
Correct |
257 ms |
12916 KB |
Output is correct |
12 |
Correct |
224 ms |
13436 KB |
Output is correct |
13 |
Correct |
220 ms |
13176 KB |
Output is correct |
14 |
Correct |
228 ms |
13400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
32 ms |
10664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
4856 KB |
Output is correct |
2 |
Correct |
28 ms |
5624 KB |
Output is correct |
3 |
Correct |
186 ms |
10536 KB |
Output is correct |
4 |
Correct |
270 ms |
12100 KB |
Output is correct |
5 |
Correct |
227 ms |
12140 KB |
Output is correct |
6 |
Correct |
228 ms |
12028 KB |
Output is correct |
7 |
Correct |
210 ms |
11976 KB |
Output is correct |
8 |
Correct |
210 ms |
11952 KB |
Output is correct |
9 |
Correct |
255 ms |
12172 KB |
Output is correct |
10 |
Correct |
221 ms |
12272 KB |
Output is correct |
11 |
Correct |
211 ms |
13384 KB |
Output is correct |
12 |
Correct |
244 ms |
13440 KB |
Output is correct |
13 |
Correct |
236 ms |
13040 KB |
Output is correct |
14 |
Correct |
226 ms |
13204 KB |
Output is correct |
15 |
Correct |
214 ms |
11952 KB |
Output is correct |
16 |
Correct |
226 ms |
12004 KB |
Output is correct |
17 |
Correct |
190 ms |
13048 KB |
Output is correct |
18 |
Correct |
232 ms |
13300 KB |
Output is correct |
19 |
Correct |
229 ms |
11988 KB |
Output is correct |
20 |
Correct |
230 ms |
12680 KB |
Output is correct |
21 |
Correct |
225 ms |
12756 KB |
Output is correct |
22 |
Correct |
269 ms |
12740 KB |
Output is correct |
23 |
Correct |
199 ms |
11884 KB |
Output is correct |
24 |
Correct |
204 ms |
12536 KB |
Output is correct |
25 |
Correct |
257 ms |
17300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
29 ms |
5672 KB |
Output is incorrect: {s, t} is wrong |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
36 ms |
5736 KB |
Output is incorrect: more than 100 calls to ask |
2 |
Halted |
0 ms |
0 KB |
- |