Submission #998878

#	Time	Username	Problem	Language	Result	Execution time	Memory
998878		PCTprobability	Highway Tolls (IOI18_highway)	C++17	51 / 100	148 ms	20028 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});
  }
  vector<int> w(m,0);
  int l=ask(w);
  vector<int> w2(m,1);
  while(true){
    int s=0;
    for(auto e:w2) s+=e;
    if(s==1) break;
    auto w3=w2;
    int s2=s/2;
    for(int j=0;j<m;j++){
      if(w3[j]){
        s2--;
        w3[j]=0;
        if(s2==0) break;
      }
    }
    int l2=ask(w3);
    if(l2==l){
      for(int j=0;j<m;j++){
        if(w3[j]==0&&w2[j]==1){
          w3[j]=1;
        }
        else if(w3[j]&&w2[j]){
          w3[j]=0;
        }
      }
    }
    w2=w3;
  }
  int u=-1,v=-1,uv=-1;
  for(int i=0;i<m;i++){
    if(w2[i]){
      u=p[i],v=q[i],uv=i;
    }
  }
  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: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31