#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100000];
int vis[100000];
void dfs(int u,vector<int>&x,vector<int>&nodes,int p,int val){
x.push_back(val);
nodes.push_back(u);
for(auto v:adj[u])if(v.first!=p)dfs(v.first,x,nodes,u,v.second);
}
pair<int,int> dis1[100000],dis2[100000];
void subgraph(int n,vector<int>u,vector<int>v,int a,int b,long long cost){
//cerr<<"work\n";
int st=0,en=u.size()-1,ans=0;
while(st<=en){
int m=(st+en)/2;
//cerr<<"m:"<<m<<" ";
vector<int>temp;
for(int i=0;i<=m;i++)temp.push_back(1);
for(int i=m+1;i<n-1;i++)temp.push_back(0);
// cerr<<temp.size()<<"\n";
long long tcost=ask(temp);
//cerr<<tcost<<"\n";
if(tcost>cost){
en=m-1;
ans=m;
}else{
st=m+1;
}
}
int bg=u[ans];
int ed=v[ans];
queue<pair<int,int> >q;
q.push({bg,0});
dis1[bg].second=dis2[bg].second=ans;
while(!q.empty()){
int x=q.front().first;
int lv=q.front().second;
q.pop();
dis1[x].first=lv;
for(auto z:adj[x])if(!dis1[z.first].first)q.push({z.first,lv+1}),dis1[z.first].second=z.second;
}
q.push({ed,0});
while(!q.empty()){
int x=q.front().first;
int lv=q.front().second;
q.pop();
dis2[x].first=lv;
for(auto z:adj[x])if(!dis2[z.first].first)q.push({z.first,lv+1}),dis2[z.first].second=z.second;
}
vector<int>temp;
vector<int>side1;
vector<int>side2;
vector<int>node1;
vector<int>node2;
for(int i=0;i<n;i++)adj[i].clear();
for(int i=0;i<n;i++){
if(i==bg)continue;
if(dis1[i].first<dis2[i].first){
adj[i].push_back({i,dis1[i].second});
}else{
adj[i].push_back({i,dis2[i].second});
}
}
//cerr<<bg<<" "<<ed<<"\n";
for(int i=0;i<n-1;i++)temp.push_back(0);
//temp[ans]=1;
//assert(ask(temp)>cost);
dfs(bg,side1,node1,ed,ans);
dfs(ed,side2,node2,bg,ans);
for(int i=0;i<n;i++)temp[i]=1;
long long cost1=ask(temp);
long long cost2=ask(temp);
int n1,n2;
st=0,en=side1.size()-1;
for(int i=0;i<n-1;i++)temp[i]=1;
for(auto x:side1)temp[x]=0;
while(st<=en){
int m=(st+en)/2;
for(int i=0;i<=m;i++)temp[side1[i]]=1;
if(ask(temp)>=cost1){
en=m-1;
n1=m;
}else{
st=m+1;
}
for(int i=0;i<=m;i++)temp[side1[i]]=0;
}
for(int i=0;i<n-1;i++)temp[i]=1;
for(auto x:side2)temp[x]=0;
st=0,en=side2.size()-1;
while(st<=en){
int m=(st+en)/2;
for(int i=0;i<=m;i++)temp[side2[i]]=1;
if(ask(temp)>=cost2){
en=m-1;
n2=m;
}else{
st=m+1;
}
for(int i=0;i<=m;i++)temp[side2[i]]=0;
}
//cerr<<node1[n1]<<" "<<node2[n2]<<"\n";
answer(node1[n1],node2[n2]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
//cerr<<"work\n";
for(int i=0;i<U.size();i++){
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
vector<int>temp;
for(int i=0;i<N-1;i++)temp.push_back(0);
if(U.size()!=N-1)return answer(rand()%N,rand()%N);
return subgraph(N,U,V,A,B,ask(temp));
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0;i<U.size();i++){
| ~^~~~~~~~~
highway.cpp:114:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if(U.size()!=N-1)return answer(rand()%N,rand()%N);
| ~~~~~~~~^~~~~
highway.cpp: In function 'void subgraph(int, std::vector<int>, std::vector<int>, int, int, long long int)':
highway.cpp:104:30: warning: 'n2' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | answer(node1[n1],node2[n2]);
| ^
highway.cpp:104:20: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | answer(node1[n1],node2[n2]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4636 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
5356 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4636 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5160 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5160 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
