#include "bits/stdc++.h"
#include "highway.h"
using namespace std;
#define int long long
pair<int,int> p[100001];
int dep[100001];
vector<pair<int,int>> adj[100001];
void dfs(int i,int pr,int id){
queue<int> q;
q.push(0);
dep[0] = 1;
while(!q.empty()){
int f = q.front();q.pop();
for(auto j:adj[f]){
if(dep[j.first]==0){
dep[j.first] = dep[f]+1;
p[j.first] = {f,j.second};
q.push(j.first);
}
}
}
}
void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B){
int m = U.size();
vector<int32_t> as(m,0);
vector<int32_t> as2(m,1);
int len = ask(as);
int len2 = ask(as2);
for(int i = 0;i<U.size();i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
dfs(0,0,-1);
answer(0,0);
vector<pair<int,int>> v;
for(int i = 0;i<N;i++){
v.push_back({dep[i],i});
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
int l = 0 , r = v.size()-2 , ans = 0;
while(l<=r){
int mid = (l+r)/2;
vector<int32_t> as(m,0);
for(int i = 0;i<=mid;i++){
as[p[v[i].second].second] = 1;
}
if(ask(as)!=len){
ans = mid;
r = mid-1;
}else l = mid+1;
}
int a = v[ans].second;
l = 2 , r = dep[a] ;int ans2 = -1;
while(l<=r){
int mid = (l+r)/2;
vector<int32_t> as(m,0);
for(int i = 0;i<N;i++){
if(dep[i]>=mid){
as[p[i].second] =1 ;
}
}
int na = ask(as);
if(na==len2){
ans2 = mid;
l = mid+1;
}else r = mid-1;
}
assert(ans2!=-1);
ans2--;
if((dep[a]-ans2)*A==len){
int x = len/A;
int b = a;
while(x--){
b = p[b].first;
}
answer(a,b);
return ;
}
vector<int> lol;
l = 0;
for(int i = 0;i<v.size();i++){
if(v[i].second==a)l = i;
if(v[i].first>ans2)r = i;
}
int ans3 = -1;
while(l<=r){
int mid = (l+r)/2;
vector<int32_t> as(m,0);
for(int i = 0;i<=mid;i++){
as[p[v[i].second].second] = 1;
}
int f = a;
while(dep[f]>v[mid].first)f = p[f].first;
as[p[f].second] = 1;
if(ask(as)>=len+(dep[a]-v[mid].first+1)*(B-A)+(B-A)){
ans3 = mid;
r = mid-1;
}else l = mid+1;
}
//assert(ans3!=-1);
if(ans3==-1){
assert(0);
}
int b = v[ans3].second;
answer(a,b);
}
Compilation message
highway.cpp: In function 'void find_pair(int32_t, std::vector<int>, std::vector<int>, int32_t, int32_t)':
highway.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0;i<U.size();i++){
| ~^~~~~~~~~
highway.cpp:84:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4948 KB |
Output is incorrect: answered not exactly once. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output is incorrect: answered not exactly once. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5720 KB |
Output is incorrect: answered not exactly once. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output is incorrect: answered not exactly once. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
11476 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11488 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
