Submission #1111944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111944		epicci23	Highway Tolls (IOI18_highway)	C++17	5 / 100	114 ms	35656 KiB

highway

#include "bits/stdc++.h"
#include "highway.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;

vector<int> v[N],Xor,depth[N],Res;
int n,m,A,B,Dist,vis[N],par[N],sub[N];

inline int oth(int c,int u) {return Xor[c] ^ u;}

void upd(int c,int d){
  sub[c]=1;
  depth[d].push_back(c);
  for(int ind:v[c]){
    int x = oth(ind,c);
  	if(ind==par[c] || vis[x]) continue;
  	par[x]=ind;
    upd(x,d+1);
    sub[c]+=sub[x];
  }
}

int we_know_root(int rt){
  for(int i=0;i<N;i++) depth[i].clear();
  par[rt]=-1;
  upd(rt,0);
  int l = 0 , r = sz(depth[Dist]) - 1;
  
  while(l<r){
  	int mid = (l+r)/2;
    Res.assign(m,0);
    for(int i=0;i<=mid;i++){
      int cur = depth[Dist][i];
      while(cur != rt){
        Res[par[cur]]=1;
        cur = oth(par[cur], cur);
      }
    }
    if(ask(Res)==Dist*B) r=mid;
    else l=mid+1;
  }

  return depth[Dist][l];
}

void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
  A=_A,B=_B;
  m = sz(U),n = _n;
  for(int i=0;i<m;i++){
  	Xor.push_back(U[i]^V[i]);
    v[U[i]].push_back(i);
    v[V[i]].push_back(i);
  }
  Res.assign(m,0);
  Dist = ask(Res) / A;
  answer(0, we_know_root(0));
}

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