#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 100000
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;
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4952 KB |
Output is correct |
2 |
Correct |
2 ms |
4952 KB |
Output is correct |
3 |
Correct |
2 ms |
5208 KB |
Output is correct |
4 |
Correct |
3 ms |
4952 KB |
Output is correct |
5 |
Correct |
3 ms |
4952 KB |
Output is correct |
6 |
Correct |
3 ms |
4952 KB |
Output is correct |
7 |
Correct |
2 ms |
5144 KB |
Output is correct |
8 |
Correct |
2 ms |
4952 KB |
Output is correct |
9 |
Correct |
2 ms |
4952 KB |
Output is correct |
10 |
Correct |
3 ms |
4952 KB |
Output is correct |
11 |
Correct |
3 ms |
4952 KB |
Output is correct |
12 |
Correct |
3 ms |
4952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5208 KB |
Output is correct |
2 |
Correct |
10 ms |
5736 KB |
Output is correct |
3 |
Correct |
77 ms |
11836 KB |
Output is correct |
4 |
Correct |
83 ms |
11764 KB |
Output is correct |
5 |
Correct |
70 ms |
11764 KB |
Output is correct |
6 |
Correct |
68 ms |
11608 KB |
Output is correct |
7 |
Correct |
89 ms |
11692 KB |
Output is correct |
8 |
Correct |
69 ms |
11712 KB |
Output is correct |
9 |
Correct |
65 ms |
11644 KB |
Output is correct |
10 |
Correct |
78 ms |
11652 KB |
Output is correct |
11 |
Correct |
90 ms |
12308 KB |
Output is correct |
12 |
Correct |
70 ms |
13360 KB |
Output is correct |
13 |
Correct |
74 ms |
13048 KB |
Output is correct |
14 |
Correct |
78 ms |
13236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
6488 KB |
Output is correct |
2 |
Correct |
18 ms |
8020 KB |
Output is correct |
3 |
Correct |
23 ms |
9496 KB |
Output is correct |
4 |
Correct |
65 ms |
16300 KB |
Output is correct |
5 |
Correct |
66 ms |
16400 KB |
Output is correct |
6 |
Correct |
82 ms |
17784 KB |
Output is correct |
7 |
Runtime error |
73 ms |
34632 KB |
Execution killed with signal 11 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5208 KB |
Output is correct |
2 |
Correct |
11 ms |
5976 KB |
Output is correct |
3 |
Correct |
60 ms |
10256 KB |
Output is correct |
4 |
Correct |
73 ms |
11552 KB |
Output is correct |
5 |
Correct |
71 ms |
11532 KB |
Output is correct |
6 |
Correct |
81 ms |
11820 KB |
Output is correct |
7 |
Correct |
66 ms |
11712 KB |
Output is correct |
8 |
Correct |
75 ms |
11620 KB |
Output is correct |
9 |
Correct |
78 ms |
12028 KB |
Output is correct |
10 |
Correct |
77 ms |
11716 KB |
Output is correct |
11 |
Correct |
76 ms |
12632 KB |
Output is correct |
12 |
Correct |
80 ms |
13800 KB |
Output is correct |
13 |
Correct |
75 ms |
13232 KB |
Output is correct |
14 |
Correct |
90 ms |
12828 KB |
Output is correct |
15 |
Correct |
72 ms |
11704 KB |
Output is correct |
16 |
Correct |
72 ms |
11444 KB |
Output is correct |
17 |
Correct |
74 ms |
12632 KB |
Output is correct |
18 |
Correct |
72 ms |
13388 KB |
Output is correct |
19 |
Correct |
86 ms |
11508 KB |
Output is correct |
20 |
Correct |
89 ms |
13872 KB |
Output is correct |
21 |
Correct |
71 ms |
12108 KB |
Output is correct |
22 |
Incorrect |
70 ms |
12152 KB |
Output is incorrect: {s, t} is wrong. |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
5464 KB |
Incorrect |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
5464 KB |
Incorrect |
2 |
Halted |
0 ms |
0 KB |
- |