Submission #1210325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210325		loiiii12358	통행료 (IOI18_highway)	C++20	12 / 100	60 ms	9768 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

int val,dep,s=0,e;
vector<int32_t> vec;
vector<pair<int,int>> pos;
vector<vector<pair<int,int>>> edges;

void run(int now,int par,int d){
  for(int i=0;i<edges[now].size();i++){
    if(edges[now][i].first==par){
      continue;
    }else if(d==dep-1){
      pos.push_back(edges[now][i]);
    }else{
      run(edges[now][i].first,now,d+1);
    }
  }
}

int search(int l,int r){
  if(l==r){
    return l;
  }
  int m=(l+r)/2;
  fill(vec.begin(),vec.end(),0);
  for(int i=0;i<=m;i++){
    vec[pos[i].second]=1;
  }
  if(ask(vec)!=val){
    return search(l,m);
  }
  return search(m+1,r);
}

void find_pair(int32_t N, std::vector<int32_t> U, std::vector<int32_t> V, int32_t A, int32_t B) {
  edges.resize(N);
  for(int i=0;i<U.size();i++){
    edges[U[i]].push_back({V[i],i});
    edges[V[i]].push_back({U[i],i});
  }
  vec.resize(U.size(),0);
  val=ask(vec);
  dep=val/A;
  run(0,-1,0);
  // cout << val << ' ' << dep << '\n';
  answer(0,pos[search(0,pos.size()-1)].first);
}

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