Submission #888438

#	Time	Username	Problem	Language	Result	Execution time	Memory
888438		kim	Highway Tolls (IOI18_highway)	C++17	51 / 100	154 ms	18596 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
#define eb emplace_back

int N,M;
vector<pii> adj[90005],adj2[90005];
vector<int> temp,ans;
pii edge[130005];
bool flag[90005];
int tour[90005],node[90005],id0;
ll mn;

void bfs(int u){
  queue<int> q;
  q.push(u);
  flag[u]=1;
  while(q.size()){
    int u=q.front(); q.pop();
    for(auto &[v,i]:adj[u]){
      if(!flag[v]){
        q.push(v);
        flag[v]=1;
        adj2[u].eb(v,i),adj2[v].eb(u,i);
      }
    }
  }
}
void dfs(int u,int p){
  tour[u]=++id0;
  node[id0]=u;
  for(auto &[v,i]:adj2[u]){
    if(v!=p) dfs(v,u);
  }
}

int play(int U){
  for(int i=0;i<N;++i) adj2[i].clear(),flag[i]=0;
  bfs(U);
  id0=0,dfs(U,U);
  int l=1,r=id0;
  while(l<r){
    int mid=l+((r-l)>>1);

    for(int i=0;i<M;++i){
      auto &[u,v]=edge[i];
      if(tour[u]<=mid&&tour[v]<=mid) temp[i]=0;
      else temp[i]=1;
    }

    if(ask(temp)==mn) r=mid;
    else l=mid+1;
  }
  ans.eb(node[l]);
  return node[l];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  ::N=N,M=U.size();
  for(int i=0;i<M;++i){
    adj[U[i]].eb(V[i],i);
    adj[V[i]].eb(U[i],i);
    edge[i]={U[i],V[i]};
    temp.eb(0);
  }
  mn=ask(temp);
  play(play(0));
  answer(ans[0],ans[1]);
}

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