#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> sorted;
vector<bool> vst;
vector<int> nDist;
void dfs(int a, int dist) {
if (vst[a]) return;
vst[a] = true;
nDist[a] = dist - 1;
for (auto &e : adj[a]) {
if (vst[e.first]) continue;
sorted.push_back({dist, e.second});
dfs(e.first, dist + 1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
int M = U.size();
adj = vector<vector<pair<int, int>>>(N);
sorted = vector<pair<int, int>>();
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
vst = vector<bool>(N);
nDist = vector<int>(N);
dfs(0, 1);
sort(sorted.begin(), sorted.end());
vector<int> tst(M);
ll ctrl = ask(tst);
int begin = 0;
int end = M - 1;
while (begin < end) {
vector<int> w(M);
int mid = (begin + end + 1) / 2;
for (int i = mid; i <= end; i++) {
w[sorted[i].second] = 1;
}
ll res = ask(w);
if (res > ctrl) {
begin = mid;
}
else {
end = mid - 1;
}
}
pair<int, int> sEdge = sorted[begin];
int S = 0;
for (int i = 0; i < N; i++) {
bool hasS = false, further = nDist[i] == sEdge.first;
for (auto &e : adj[i]) {
if (e.second == sEdge.second) hasS = true;
}
if (hasS && further) {
S = i;
break;
}
}
//cout << S << '\n';
vst = vector<bool>(N);
nDist = vector<int>(N);
sorted = vector<pair<int, int>>();
dfs(S, 1);
sort(sorted.begin(), sorted.end());
begin = -1;
for (int i = 0; i < M; i++) {
if (sorted[i].first == ctrl / A && begin == -1) begin = i;
if (sorted[i].first == ctrl / A) end = i;
}
while (begin < end) {
vector<int> w(M);
int mid = (begin + end + 1) / 2;
for (int i = mid; i <= end; i++) {
w[sorted[i].second] = 1;
}
ll res = ask(w);
if (res > ctrl) {
begin = mid;
}
else {
end = mid - 1;
}
}
pair<int, int> tEdge = sorted[begin];
int T = 0;
for (int i = 0; i < N; i++) {
bool hasT = false, further = nDist[i] == tEdge.first;
for (auto &e : adj[i]) {
if (e.second == tEdge.second) hasT = true;
}
if (hasT && further) {
T = i;
break;
}
}
answer(S, T);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
2 |
Correct |
6 ms |
1456 KB |
Output is correct |
3 |
Correct |
112 ms |
9772 KB |
Output is correct |
4 |
Correct |
109 ms |
9580 KB |
Output is correct |
5 |
Correct |
96 ms |
9776 KB |
Output is correct |
6 |
Correct |
91 ms |
9780 KB |
Output is correct |
7 |
Correct |
102 ms |
9572 KB |
Output is correct |
8 |
Correct |
106 ms |
9776 KB |
Output is correct |
9 |
Correct |
87 ms |
9592 KB |
Output is correct |
10 |
Correct |
101 ms |
9596 KB |
Output is correct |
11 |
Correct |
87 ms |
10352 KB |
Output is correct |
12 |
Correct |
87 ms |
11380 KB |
Output is correct |
13 |
Correct |
96 ms |
10724 KB |
Output is correct |
14 |
Correct |
88 ms |
10732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
1968 KB |
Output is correct |
2 |
Correct |
17 ms |
3640 KB |
Output is correct |
3 |
Correct |
26 ms |
5060 KB |
Output is correct |
4 |
Correct |
78 ms |
14732 KB |
Output is correct |
5 |
Correct |
70 ms |
14764 KB |
Output is correct |
6 |
Correct |
81 ms |
14776 KB |
Output is correct |
7 |
Correct |
70 ms |
14760 KB |
Output is correct |
8 |
Correct |
71 ms |
14828 KB |
Output is correct |
9 |
Correct |
68 ms |
14736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
9 ms |
1368 KB |
Output is correct |
3 |
Correct |
67 ms |
7892 KB |
Output is correct |
4 |
Correct |
88 ms |
9588 KB |
Output is correct |
5 |
Correct |
89 ms |
9564 KB |
Output is correct |
6 |
Correct |
90 ms |
9600 KB |
Output is correct |
7 |
Correct |
88 ms |
9588 KB |
Output is correct |
8 |
Correct |
99 ms |
9580 KB |
Output is correct |
9 |
Correct |
86 ms |
9772 KB |
Output is correct |
10 |
Correct |
98 ms |
9772 KB |
Output is correct |
11 |
Correct |
79 ms |
10328 KB |
Output is correct |
12 |
Correct |
84 ms |
11120 KB |
Output is correct |
13 |
Correct |
85 ms |
10628 KB |
Output is correct |
14 |
Correct |
81 ms |
11100 KB |
Output is correct |
15 |
Correct |
87 ms |
9584 KB |
Output is correct |
16 |
Correct |
83 ms |
9696 KB |
Output is correct |
17 |
Correct |
84 ms |
10840 KB |
Output is correct |
18 |
Correct |
79 ms |
10852 KB |
Output is correct |
19 |
Correct |
86 ms |
9864 KB |
Output is correct |
20 |
Correct |
84 ms |
11612 KB |
Output is correct |
21 |
Correct |
69 ms |
10096 KB |
Output is correct |
22 |
Correct |
81 ms |
10088 KB |
Output is correct |
23 |
Correct |
82 ms |
9864 KB |
Output is correct |
24 |
Correct |
80 ms |
10488 KB |
Output is correct |
25 |
Correct |
89 ms |
14200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
1544 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
1544 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |