#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=90000+10;
long long n,a,b,aval,s,t;
long long m,sz[maxn],vis[maxn];
vector<long long>adj[maxn];
struct yal{
long long u,v;
long long getad(long long fu){
return (fu^v^u);
}
}alle[maxn];
long long pors(vector<long long>er){
vector<int>ret(m);
for(auto x:er){
ret[x]=1;
}
return ask(ret);
}
void calsz(long long u,long long par=-1){
sz[u]=1;
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(vis[v]==0&&v!=par){
calsz(v,u);
sz[u]+=sz[v];
}
}
}
long long findcen(long long u,long long szz,long long par=-1){
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(vis[v]==0&&sz[v]*2>szz&&v!=par){
return findcen(v,szz,u);
}
}
return u;
}
vector<long long>ersa;
int f=0;
int had=0;
void go(int u,int par=-1){
if(u==had){
f=1;
}
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v==par||vis[v]){
continue;
}
ersa.push_back(x);
go(v,u);
}
}
long long finds(long long u=0){
// cout<<u<<endl;
calsz(u);
// cout<<u<<endl;
long long v=findcen(u,sz[u]);
// cout<<u<<endl;
vector<long long>tof;
ersa.clear();
for(auto x:adj[v]){
long long z=alle[x].getad(v);
if(vis[z]==0){
tof.push_back(x);
ersa.push_back(tof.back());
go(alle[tof.back()].getad(v),v);
}
}
long long fake=pors(tof);
if(fake==aval){
vis[v]=1;
return finds(u);
}
if(fake-b+a==aval){
return v;
}
long long low=-1,high=(long long)tof.size()-1,mid;
for(int i=0;i<(int)tof.size();i++){
f=0;
had=u;
go(alle[tof[i]].getad(v),v);
if(f){
vector<long long>hey;
for(int j=0;j<(int)tof.size();j++){
if(j==i){
continue;
}
hey.push_back(tof[j]);
}
tof=hey;
break;
}
}
while(high-low>1){
mid=(high+low)>>1;
ersa.clear();
for(long long i=0;i<=mid;i++){
ersa.push_back(tof[i]);
go(alle[tof[i]].getad(v),v);
}
fake=pors(ersa);
if(fake==aval){
low=mid;
}else{
high=mid;
}
}
// cout<<u<<" "<<v<<endl;
vis[v]=1;
return finds(alle[tof[high]].getad(v));
}
vector<long long>ham;
long long bal[maxn];
void dfscal(long long u,long long len,long long par=-1,long long now=0){
if(now==len){
ham.push_back(u);
return ;
}
for(auto x:adj[u]){
long long v=alle[x].getad(u);
if(v==par){
continue;
}
bal[v]=x;
dfscal(v,len,u,now+1);
}
}
long long findt(){
dfscal(s,aval/a);
long long low=-1,high=(long long)ham.size()-1,mid;
while(high-low>1){
vector<long long>ers;
mid=(high+low)>>1;
for(long long i=0;i<=mid;i++){
ers.push_back(bal[ham[i]]);
}
long long fake=pors(ers);
if(fake==aval){
low=mid;
}else{
high=mid;
}
}
return ham[high];
}
void calc(){
// cout<<"av"<<endl;
s=finds();
//s=0;
// cout<<"dov"<<endl;
t=findt();
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n=N;
m = U.size();
a=A;
b=B;
for(long long i=0;i<m;i++){
alle[i].u=U[i];
alle[i].v=V[i];
adj[U[i]].push_back(i);
adj[V[i]].push_back(i);
}
if(m!=n-1){
answer(0,1);
return ;
}
aval=pors({});
calc();
//cout<<s<<" "<<t<<endl;
answer(s,t);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
4440 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4440 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
5720 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
7 ms |
4880 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4952 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
