Submission #998890

#	Time	Username	Problem	Language	Result	Execution time	Memory
998890		PCTprobability	Highway Tolls (IOI18_highway)	C++17	30 / 100	155 ms	19028 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
vector<pair<int,int>> g[101010];
vector<pair<int,int>> t[2][101010];
void find_pair(int n, std::vector<int> p, std::vector<int> q, int a, int b) {
  int m=p.size();
  for(int i=0;i<m;i++){
    g[p[i]].push_back({q[i],i});
    g[q[i]].push_back({p[i],i});
  }
  int ok=0,ng=m;
  vector<int> w(m,0);
  int l=ask(w);
  while(abs(ok-ng)>1){
    int mid=(ok+ng)/2;
    vector<int> w2(m);
    for(int i=0;i<mid;i++) w2[i]=1;
    if(ask(w2)==l) ok=mid;
    else ng=mid;
  }
  int u=p[ok],v=q[ok],uv=ok;
  queue<int> qu;
  qu.push(u);
  qu.push(v);
  vector<int> seen(n,0);
  vector<int> d(n,0);
  vector<int> id(n,-1);
  //u,v それぞれ最短路
  seen[u]=1;
  seen[v]=2;
  while(qu.size()){
    int nv=qu.front();
    qu.pop();
    for(auto e:g[nv]){
      if(seen[e.fi]==0){
        seen[e.fi]=seen[nv];
        d[e.fi]=d[nv]+1;
        qu.push(e.fi);
        id[e.fi]=e.se;
        t[seen[e.fi]][e.fi].pb({nv,e.se});
      }
    }
  }
  int s=-1,t=-1;
  for(int ty=1;ty<=2;ty++){
    vector<pair<int,int>> vs;
    for(int i=0;i<n;i++){
      if(seen[i]==ty) vs.pb({d[i],i});
    }
    sort(vs.begin(),vs.end());
    while(vs.size()>1){
      int m2=vs.size();
      int mid=m2/2;
      vector<int> as(m,1);
      as[uv]=0;
      for(int i=0;i<n;i++) if(id[i]>=0) as[id[i]]=0;
      for(int i=mid;i<m2;i++) as[id[vs[i].se]]=1;
      int l2=ask(as);
      if(l2==l){
        for(int i=mid;i<m2;i++) vs.pop_back();
      }
      else{
        reverse(vs.begin(),vs.end());
        for(int i=0;i<mid;i++) vs.pop_back();
        reverse(vs.begin(),vs.end());
      }
    }
    if(ty==1) s=vs[0].se;
    else t=vs[0].se;
  }
  answer(s,t);
}

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