#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 100000;
vector<pi>tree[sz+5];
int visited[sz+5];
int dist_a[sz+5],dist_b[sz+5];
int FIND(vector<int>w,vector<int>candidates,int root,int edge,ll d){
memset(visited,0,sizeof(visited));
for(int i=0; i<w.size(); i++) w[i] = 1;
w=vector<int>(w.size(),1);
visited[root] = 0;
queue<int>q; q.push(root);
vector<pi>v; v.emplace_back(pi(root,edge));
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(visited[nxt]){
visited[nxt] = 0;
v.emplace_back(pi(nxt,id));
q.push(nxt);
}
}
}
reverse(v.begin(),v.end());
for(pi p : v) w[p.second]=0;
d=ask(w);
int l = 0,r = v.size()-1;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[v[i].second] = 1;
if(ask(w) > d) r = M-1;
else l = M+1;
for(int i=0; i<=M; i++) w[v[i].second] = 0;
}
return v[l].first;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
for(int i=0; i<n; i++){
tree[i].clear();
visited[i] = 0;
dist_a[i] = dist_b[i] = 1e9;
}
int m = U.size();
for(int i=0; i<U.size(); i++){
int a = U[i],b = V[i];
tree[a].emplace_back(pi(b,i));
tree[b].emplace_back(pi(a,i));
}
vector<int>w(m,0);
ll d = ask(w);
int l = 0,r = m-1;
while(l<=r){
int M = (l+r)>>1;
for(int i=0; i<=M; i++) w[i] = 1;
if(ask(w)==d) l = M+1;
else r = M-1;
for(int i=0; i<=M; i++) w[i] = 0;
}
int e = l;
int a = U[e],b = V[e];
dist_a[a] = 0;
queue<int>q; q.push(a);
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(dist_a[nxt] > dist_a[cur] + 1){
dist_a[nxt] = dist_a[cur] + 1;
q.push(nxt);
}
}
}
dist_b[b] = 0;
q.push(b);
while(!q.empty()){
int cur = q.front(); q.pop();
for(pi p : tree[cur]){
int nxt = p.first;
int id = p.second;
if(dist_b[nxt] > dist_b[cur] + 1){
dist_b[nxt] = dist_b[cur] + 1;
q.push(nxt);
}
}
}
vector<int>c;
for(int i=0; i<n; i++){
if(dist_a[i] < dist_b[i]) c.emplace_back(i);
}
a = FIND(w,c,a,e,d); c.clear();
for(int i=0; i<n; i++){
if(dist_b[i] < dist_a[i]) c.emplace_back(i);
}
b = FIND(w,c,b,e,d); c.clear();
answer(a,b);
}
Compilation message
highway.cpp: In function 'int FIND(std::vector<int>, std::vector<int>, int, int, ll)':
highway.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i=0; i<w.size(); i++) w[i] = 1;
| ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0; i<U.size(); i++){
| ~^~~~~~~~~
highway.cpp:73:8: warning: unused variable 'id' [-Wunused-variable]
73 | int id = p.second;
| ^~
highway.cpp:86:8: warning: unused variable 'id' [-Wunused-variable]
86 | int id = p.second;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
3160 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3160 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3872 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3160 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3928 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3928 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
