제출 #1032846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032846		amirhoseinfar1385	통행료 (IOI18_highway)	C++17	0 / 100	7 ms	5720 KiB

highway

#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;
}

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;
  for(auto x:adj[v]){
    long long z=alle[x].getad(v);
    if(vis[z]==0){
      tof.push_back(x);
    }
  }
  long long fake=pors(tof);
  if(fake==aval){
    return v;
  }
  long long low=-1,high=(long long)tof.size(),mid;
  while(high-low>1){
    mid=(high+low)>>1;
    vector<long long>ers;
    for(long long 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<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);
}

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