Submission #124737

#	Time	Username	Problem	Language	Result	Execution time	Memory
124737		dragonslayerit	Highway Tolls (IOI18_highway)	C++14	90 / 100	369 ms	16892 KiB

highway

#include "highway.h"
#include <queue>
#include <stdint.h>
#include <cstdio>
#include <algorithm>

static const int INF=1e9+7;

static void dfs(int node,int parent,const std::vector<int>& elist,const std::vector<std::vector<int> >& adj,
		std::vector<int>& post){
  for(int e:adj[node]){
    int child=elist[e^1];
    if(child==parent) continue;
    dfs(child,node,elist,adj,post);
    post.push_back(e^1);
  }
}

static int find_first_vertex(const std::vector<int>& elist,const std::vector<std::vector<int> >& adj,int64_t base,const std::vector<int>& mask,int root){
  std::vector<int> post;
  dfs(root,root,elist,adj,post);
  /*
  printf("postorder:\n");
  for(int i=0;i<post.size();i++){
    printf(" %d=>%d\n",elist[post[i]],elist[post[i]^1]);
  }
  */
  int low=0,high=post.size();
  while(high-low>1){
    int mid=(low+high)/2;
    std::vector<int> ws(mask);
    for(int i=0;i<mid;i++){
      ws[post[i]>>1]=1;
    }
    if(ask(ws)>base){
      high=mid;
    }else{
      low=mid;
    }
  }
  //printf("critical tree edge: %d=>%d\n",elist[post[low]],elist[post[low]^1]);
  return elist[post[low]];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();
  int64_t base=ask(std::vector<int>(M));
  //printf("BASE=%ld\n",base);
  std::vector<int> elist;
  std::vector<std::vector<int> > adj(N);
  for(int i=0;i<M;i++){
    elist.push_back(U[i]);
    elist.push_back(V[i]);
    adj[U[i]].push_back(i*2);
    adj[V[i]].push_back(i*2+1);
  }
  int low=0,high=M;
  while(high-low>1){
    int mid=(low+high)/2;
    std::vector<int> ws(M);
    for(int i=0;i<mid;i++){
      ws[i]=1;
    }
    if(ask(ws)>base){
      high=mid;
    }else{
      low=mid;
    }
  }
  //printf("critical: %d<=>%d\n",U[low],V[low]);
  std::vector<int> from(N);
  std::queue<int> frontier;
  std::vector<int> dist(N,INF);
  dist[U[low]]=0;
  frontier.push(U[low]);
  dist[V[low]]=0;
  frontier.push(V[low]);  
  while(!frontier.empty()){
    int node=frontier.front();
    frontier.pop();
    for(int e:adj[node]){
      if((e>>1)<low) continue;
      int child=elist[e^1];
      if(dist[child]==INF){
	dist[child]=dist[node]+1;
	from[child]=e;
	frontier.push(child);
      }
    }
  }
  std::vector<int> ws(M,1);
  adj.clear();
  adj.resize(N);
  for(int i=0;i<N;i++){
    if(dist[i]!=0&&dist[i]!=INF){
      int e=from[i];
      int U=elist[e];
      int V=elist[e^1];
      adj[U].push_back(e);
      adj[V].push_back(e^1);
      ws[e>>1]=0;
    }
  }
  adj[U[low]].push_back(low*2);
  adj[V[low]].push_back(low*2+1);
  ws[low]=0;
  int S=find_first_vertex(elist,adj,base,ws,U[low]);
  int T=find_first_vertex(elist,adj,base,ws,S);
  //printf("S=%d, T=%d\n",S,T);
  answer(S,T);
}

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