Submission #1032837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032837		amirhoseinfar1385	Highway Tolls (IOI18_highway)	C++17	0 / 100	8 ms	3928 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=90000+10;
int n,a,b,aval,s,t;
int m,sz[maxn],vis[maxn];
vector<int>adj[maxn];

struct yal{
  int u,v;
  int getad(int fu){
    return (fu^v^u);
  }
}alle[maxn];

int pors(vector<int>er){
  vector<int>ret(m);
  for(auto x:er){
    ret[x]=1;
  }
  return ask(ret);
}

void calsz(int u,int par=-1){
  sz[u]=1;
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(vis[v]==0&&v!=par){
      calsz(v,u);
      sz[u]+=sz[v];
    }
  }
}

int findcen(int u,int szz,int par=-1){
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(vis[v]==0&&sz[v]*2>szz&&v!=par){
      return findcen(v,szz,u);
    }
  }
  return u;
}

int finds(int u=0){
 // cout<<u<<endl;
  calsz(u);
 // cout<<u<<endl;
  int v=findcen(u,sz[u]);
 // cout<<u<<endl;
  vector<int>tof;
  for(auto x:adj[v]){
    int z=alle[x].getad(v);
    if(vis[z]==0){
      tof.push_back(x);
    }
  }
  int fake=pors(tof);
  if(fake==aval){
    return v;
  }
  int low=-1,high=(int)tof.size(),mid;
  while(high-low>1){
    mid=(high+low)>>1;
    vector<int>ers;
    for(int i=0;i<=mid;i++){
      ers.push_back(tof[i]);
    }
    fake=pors(ers);
    if(fake==aval){
      low=mid;
    }else{
      high=mid;
    }
  }
  vis[v]=1;
  return finds(alle[tof[high]].getad(v));
}
vector<int>ham;
int bal[maxn];

void dfscal(int u,int len,int par=-1,int now=0){
  if(now==len){
    ham.push_back(u);
    return ;
  }
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(v==par){
      continue;
    }
    dfscal(v,len,u,now+1);
  }
}

int findt(){
  dfscal(s,aval/a);
  int low=-1,high=(int)ham.size()-1,mid;
  while(high-low>1){
    vector<int>ers;
    mid=(high+low)>>1;
    for(int 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();
 // 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(int 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();
  answer(s,t);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31