#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "highway.h"
#endif
using namespace std;
using ll = long long;
int n;
const int MAXN=90000;
int cur_tree_size;
int sz[MAXN]; // subtree size
bool exists[MAXN];
vector<pair<int,int>> adj[MAXN];
bool c_vis[MAXN];
bool mark_vis[MAXN];
bool mark_one=0;
int c;
ll first_ask;
ll second_ask;
bool using_subtree[MAXN];
vector<pair<int,int>> candid_a; // the candidates <vertex,relevant_edge>
vector<pair<int,int>> candid_b;
bool final_vis[MAXN];
int a_dis[MAXN];
int b_dis[MAXN];
vector<int> ask_one(MAXN-1);
vector<int> ask_two(MAXN-1);
int the_a_dis;
int the_b_dis;
#ifdef ARTHUR_LOCAL
ll ask(vector<int> V)
{
if(V[0]==1) return 2;
else return 1;
}
void answer(int a, int b)
{
cout <<"YEAHHH" << a << " " << b << endl;
}
#endif
void sz_dfs(int v)
{
sz[v]++;
for(auto u:adj[v])
{
if(sz[u.first]!=0 || !exists[u.first]) continue; // does this make the code work
sz_dfs(u.first);
sz[v]+=sz[u.first];
}
}
int c_dfs(int v)
{
c_vis[v]=1;
for(auto u:adj[v])
{
if(c_vis[u.first] || !exists[u.first]) continue;
if(sz[u.first] > int(cur_tree_size/2)) return c_dfs(u.first);
}
return v;
}
void mark_dfs(int v)
{
mark_vis[v]=1;
for(auto u:adj[v])
{
if(mark_vis[u.first] || !exists[u.first]) continue;
if(mark_one) ask_one[u.second]=1;
else ask_two[u.second]=1;
}
}
void exist_dfs(int v)
{
exists[v]=0;
for(auto u:adj[v])
{
if(!exists[u.first] || u.first==c) continue;
exist_dfs(u.first);
}
}
void a_dfs(int v)
{
final_vis[v]=1;
for(auto u:adj[v])
{
if(final_vis[u.first] || !exists[u.first]) continue;
a_dis[u.first]=a_dis[v]+1;
if(a_dis[u.first] == the_a_dis) candid_a.push_back(make_pair(u.first,u.second));
a_dfs(u.first);
}
}
void b_dfs(int v)
{
final_vis[v]=1;
for(auto u:adj[v])
{
if(final_vis[u.first] || !exists[u.first]) continue;
b_dis[u.first]=b_dis[v]+1;
if(b_dis[u.first] == the_b_dis) candid_b.push_back(make_pair(u.first,u.second));
b_dfs(u.first);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
// initialise things
n=N;
for(int i=0; i<n-1; i++)
{
adj[U[i]].push_back({V[i],i});
adj[V[i]].push_back({U[i],i});
}
for(int i=0; i<n; i++) exists[i]=1;
// okay now figure out the 'base distance'
vector<int> base_w(n-1); // should be initialised with all zeroes
ll path_length = ask(base_w);
// do some more initialisation ...
cur_tree_size=n;
int root=-1;
c=0;
while(true) // continually discards >= 1/4 of the current graph
{
for(int i=0; i<n; i++)
{
sz[i]=0;
c_vis[i]=0;
}
sz_dfs(c);
c = c_dfs(c);
//cout << "CENTROID: " << c << endl;
// cout << "SIZES" << endl;
// for(int i=0; i<n; i++) cout << sz[i] << " ";
//cout << endl;
vector<pair<int,int>> subtrees;
for(auto u:adj[c])
{
if(sz[u.first]>sz[c])
{
subtrees.push_back({cur_tree_size-sz[c],u.first});
// cout << u.first << " has a subtree of size " << cur_tree_size-sz[c] << endl;
}
else
{
//cout << u.first << " has a subtree of size " << sz[u.first] << endl;
subtrees.push_back({sz[u.first],u.first});
}
}
sort(subtrees.rbegin(),subtrees.rend()); // so the largest subtrees are first
vector<int> subtrees_used;
// vector<bool> using_subtree(MAXN);
for(int i=0; i<n; i++) using_subtree[i]=0;
int cur_subtree_total_size=1;
for(auto u:subtrees)
{
if(cur_subtree_total_size > int(cur_tree_size/4)) break; // this is causing problems because in really small trees (size < 4)
cur_subtree_total_size += u.first;
subtrees_used.push_back(u.second);
using_subtree[u.second]=1;
//cout << u.first << " " << u.second << "are being used" << endl;
}
for(int i=0; i<n-1; i++)
{
ask_one[i]=0;
ask_two[i]=0;
mark_vis[i]=0;
mark_vis[i+1]=0;
}
for(auto u:adj[c])
{
if(!exists[u.first]) continue;
if(using_subtree[u.first]) ask_one[u.second]=1;
else ask_two[u.second]=1; // I think that this is correct
mark_one = using_subtree[u.first];
mark_dfs(u.first);
}
//for(int i=0; i<n-1; i++) cout << ask_one[i] << " ";
//cout << endl;
//for(int i=0; i<n-1; i++) cout << ask_two[i] << " ";
//cout << endl;
first_ask = ask(ask_one);
second_ask = ask(ask_two);
// okay so now we have a vertex which we know the
// path passes through, and the division of which
// vertices exiting it are on which side
if(min(first_ask,second_ask) > path_length)
{
root=c;
break;
}
for(auto u:adj[c])
{
if(using_subtree[u.first])
{
//cout << u.first << endl;
if(first_ask==path_length) exist_dfs(u.first);
}
else
{
if(second_ask==path_length) exist_dfs(u.first);
}
}
//cout << "ASKS" << endl;
//cout << first_ask << " " << second_ask << " " << path_length << endl;
//cout << "EXISTENT" << endl;
//for(int i=0; i<n; i++) cout << exists[i] << " ";
//cout << endl;
cur_tree_size=0;
for(int i=0; i<n; i++)
{
if(exists[i]) cur_tree_size++;
}
if(cur_tree_size<4) break;
}
// okay so now we have the two cases: the 'root' and the tree size < 4
if(root!=-1)
{
the_a_dis = ll((first_ask - path_length)/ll(B-A));
the_b_dis = ll((second_ask - path_length)/ll(B-A));
for(auto u:adj[c])
{
if(!exists[u.first]) continue;
if(using_subtree[u.first]) a_dfs(u.first);
else b_dfs(u.first);
}
// uhhh ... now we need to do the two 'binary searches'
int pass=candid_a.size()-1;
int fail=-1;
while(pass-fail>1)
{
int mid = (pass+fail)/2;
vector<int> askin(n-1);
for(int i=0; i<=mid; i++)
{
askin[candid_a[i].second]=1;
}
int cur_ans = ask(askin);
if(cur_ans == path_length)
{
fail = mid;
}
else
{
pass = mid;
}
}
int first_part = pass;
pass=candid_b.size()-1;
fail=-1;
while(pass-fail>1)
{
int mid = (pass+fail)/2;
vector<int> askin(n-1);
for(int i=0; i<=mid; i++)
{
askin[candid_b[i].second]=1;
}
int cur_ans = ask(askin);
if(cur_ans == path_length)
{
fail = mid;
}
else
{
pass = mid;
}
}
answer(first_part,pass);
return;
}
else
{
// brute force all possibilities on the 2/3 vertex graph
vector<int> vert;
for(int i=0; i<n; i++)
{
if(exists[i]) vert.push_back(i);
}
//cout << vert.size() << endl;
if(vert.size()==2)
{
answer(vert[0],vert[1]);
return;
}
int middle;
int adj_guy=-1;
int deg=0;
for(auto u:adj[vert[0]])
{
if(u.first == vert[1] || u.first == vert[2])
{
adj_guy=u.first;
deg++;
}
}
if(deg==2) middle=vert[0];
else middle = adj_guy;
//cout << middle << endl;
int side1=-1;
int side2=-1;
for(auto u:vert)
{
// cout << u <<"!"<<endl;
if(u!=middle && side1==-1) side1=u;
else
{
if(u!=middle) side2=u;
}
}
int edge1=-1;
int edge2=-1;
for(auto u:adj[middle])
{
if(u.first==side1) edge1=u.second;
if(u.first==side2) edge2=u.second;
}
// cout << edge1 << " " << edge2 << endl;
vector<int> askin(n-1);
askin[edge1]=1;
askin[edge2]=1;
if(ask(askin) == ll(B+B))
{
answer(side1,side2);
return;
}
askin[edge2]=0;
if(ask(askin) == ll(B))
{
answer(middle,side1);
return;
}
answer(middle,side2);
return;
}
/* int M = U.size();
for (int j = 0; j < 50; ++j) {
std::vector<int> w(M);
for (int i = 0; i < M; ++i) {
w[i] = 0;
}
long long toll = ask(w);
}
answer(0, N - 1);*/
}
#ifdef ARTHUR_LOCAL
int main()
{
find_pair(5,{0,1,2,2},{1,2,3,4},1,2);
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3064 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3304 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
4136 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3220 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
3636 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
3632 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
