#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
int n, m;
vector<int> pe;
vector<int> dep;
vector<vector<pair<int, int>>> g;
void Dfs (int v, int p) {
for (auto [u, i] : g[v]) {
if (u == p) {
continue;
}
pe[u] = i;
dep[u] = dep[v] + 1;
Dfs(u, v);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
g.resize(n);
pe.resize(n);
dep.resize(n);
m = (int) U.size();
for (int i = 0; i < m; ++i) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
}
Dfs(0, 0);
vector<int> vec;
vector<int> w(m, 0);
long long dis = ask(w);
int depT = dis / A;
for (int i = 0; i < n; ++i) {
if (dep[i] == depT) {
vec.push_back(i);
}
}
auto fix = [&](vector<int> nodes) {
vector<int> ret(m);
for (int u : nodes) {
ret[pe[u]] = true;
}
return ret;
};
while (vec.size() > 1) {
vector<int> lx, rx;
int mid = (int) vec.size() / 2;
for (int i = 0; i < mid; ++i) {
lx.push_back(vec[i]);
}
for (int i = mid; i < (int) vec.size(); ++i) {
rx.push_back(vec[i]);
}
if (ask(fix(lx)) > dis) {
vec = lx;
} else {
vec = rx;
}
}
assert(!vec.empty());
answer(0, vec[0]);//S, T
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Correct |
0 ms |
208 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
208 KB |
Output is correct |
12 |
Correct |
1 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
8 ms |
1232 KB |
Output is correct |
3 |
Correct |
79 ms |
8728 KB |
Output is correct |
4 |
Correct |
72 ms |
8660 KB |
Output is correct |
5 |
Correct |
56 ms |
8720 KB |
Output is correct |
6 |
Correct |
78 ms |
8564 KB |
Output is correct |
7 |
Correct |
70 ms |
8656 KB |
Output is correct |
8 |
Correct |
83 ms |
8708 KB |
Output is correct |
9 |
Correct |
59 ms |
8616 KB |
Output is correct |
10 |
Correct |
89 ms |
8732 KB |
Output is correct |
11 |
Correct |
81 ms |
9056 KB |
Output is correct |
12 |
Correct |
92 ms |
9504 KB |
Output is correct |
13 |
Correct |
92 ms |
9084 KB |
Output is correct |
14 |
Correct |
56 ms |
8696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
1488 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
201 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
179 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |