#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int p;
vector<pair<node*, int>> l;
int d;
};
void dfs(node* n, node* p, int d){
n->d = d;
for(auto [c,x] : n->l){
if(c==p) continue;
c->p = x;
dfs(c, n, d+1);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
node g[N];
int m = U.size();
for(int i = 0;i < U.size();i++){
g[U[i]].l.emplace_back(&g[V[i]], i);
g[V[i]].l.emplace_back(&g[U[i]], i);
}
dfs(&g[0], NULL, 0);
vector<int> w(m, 0);
long long dis = ask(w)/A;
vector<pair<int, int>> v;
for(int i = 1;i < N;i++) if(g[i].d == dis) v.emplace_back(g[i].p, i);
int l = 0, r = v.size()-1, mid;
while(l<r){
mid = l+r>>1;
for(int i = l;i <= mid;i++) w[v[i].first] = 1;
long long re = ask(w);
for(int i = l;i <= mid;i++) w[v[i].first] = 0;
if(re > dis*A){
r = mid;
} else l = mid+1;
}
answer(0, v[l].second);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i = 0;i < U.size();i++){
| ~~^~~~~~~~~~
highway.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | mid = l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 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 |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 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 |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
7 ms |
1520 KB |
Output is correct |
3 |
Correct |
71 ms |
10548 KB |
Output is correct |
4 |
Correct |
75 ms |
10532 KB |
Output is correct |
5 |
Correct |
72 ms |
10536 KB |
Output is correct |
6 |
Correct |
92 ms |
10396 KB |
Output is correct |
7 |
Correct |
65 ms |
10448 KB |
Output is correct |
8 |
Correct |
81 ms |
10556 KB |
Output is correct |
9 |
Correct |
65 ms |
10352 KB |
Output is correct |
10 |
Correct |
76 ms |
10544 KB |
Output is correct |
11 |
Correct |
72 ms |
10832 KB |
Output is correct |
12 |
Correct |
92 ms |
11108 KB |
Output is correct |
13 |
Correct |
82 ms |
10860 KB |
Output is correct |
14 |
Correct |
73 ms |
10812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
1536 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output is incorrect: {s, t} is wrong. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
309 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
281 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |