#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 200000
using namespace std;
/*
ll ask(vi arr) {
for (int x:arr)cout<<x<<" ";
cout<<'\n';
ll res;
cin>>res;
return res;
}
void answer(int x,int y) {
cout<<x<<" "<<y<<"\n";
}
*/
vi edges;
vvp adj(MAXN+1);
vvp depth(MAXN+1);
void dfs(int v,int p,int d) {
for (auto &[to,id]:adj[v]) {
if (to==p)continue;
depth[d].pb({to,id});
edges.pb(id);
dfs(to,v,d+1);
}
}
void find_pair(int n,vi U,vi V,int A,int B) {
for (int i=0;i<n-1;i++) {
adj[U[i]].pb({V[i],i});
adj[V[i]].pb({U[i],i});
}
vi w(n-1);
ll dist=ask(w);
int res=-1;
for (int bit=15;bit>=0;bit--) {
if (res+(1<<bit)>=n-1)continue;
for (int i=0;i<=res+(1<<bit);i++)w[i]=1;
ll cur=ask(w);
for (int i=0;i<=res+(1<<bit);i++)w[i]=0;
if (cur==dist)res+=(1<<bit);
}
res++;
cout<<V[res]<<" "<<U[res]<<'\n';
depth[0].pb({V[res],res});
dfs(V[res],U[res],1);
for (int x:edges)w[x]=1;
ll distx=( ask (w) - dist ) / ( B - A );
for (int x:edges)w[x]=0;
ll disty= dist/A - distx - 1;
cout<<distx<<" "<<disty<<"\n";
int idx=-1;
for (int bit=15;bit>=0;bit--) {
if ( idx+(1<<bit) >= depth[distx].size() )continue;
for (int i=0;i<=idx+(1<<bit);i++)w[depth[distx][i].S]=1;
ll cur=ask(w);
for (int i=0;i<=idx+(1<<bit);i++)w[depth[distx][i].S]=0;
if (cur == dist )idx+=(1<<bit);
}
idx=depth[distx][idx+1].F;
depth.assign(MAXN+1,{});
depth[0].pb({U[res],res});
dfs(U[res],V[res],1);
int idy=-1;
for (int bit=15;bit>=0;bit--) {
if ( idy+(1<<bit) >= depth[disty].size() )continue;
for (int i=0;i<=idy+(1<<bit);i++)w[depth[disty][i].S]=1;
ll cur=ask(w);
for (int i=0;i<=idy+(1<<bit);i++)w[depth[disty][i].S]=0;
if (cur == dist )idy+=(1<<bit);
}
idy=depth[disty][idy+1].F;
answer(idx,idy);
}
/*
signed main() {
int n;
cin>>n;
vi V,U;
for (int i=0;i<n-1;i++) {
int u,v;
cin>>u>>v;
V.pb(v);
U.pb(u);
}
int A,B;
cin>>A>>B;
find_pair(n,U,V,A,B);
}
*/
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if ( idx+(1<<bit) >= depth[distx].size() )continue;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
highway.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if ( idy+(1<<bit) >= depth[disty].size() )continue;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
9816 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9816 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
11096 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
9816 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10328 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
10328 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
