제출 #1237186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237186		mychecksedad	Highway Tolls (IOI18_highway)	C++20	12 / 100	50 ms	11132 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 2e5+100;

vector<pii> g[N];
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();

  for(int i = 0; i < m; ++i){
    g[U[i]].pb({V[i], i});
    g[V[i]].pb({U[i], i});
  }

  vi w(m);
  ll val = ask(w);
  int k = val / A;
  
  vector<bool> vis(n);
  queue<int> q;
  vi dist(n);
  q.push(0);
  vis[0] = 1;
  vi T, par(n);
  while(!q.empty()){
    int v = q.front(); q.pop();
    if(dist[v] == k) T.pb(v);
    for(auto [u, id]: g[v]){
      if(!vis[u]){
        par[u] = id;
        dist[u] = dist[v] + 1;
        q.push(u);
        vis[u] = 1;
      }
    }
  }

  int l = 0, r = int(T.size()) - 2, res = int(T.size())-1;
  while(l <= r){
    int mid = l+r>>1;
    w.clear();
    w.resize(m, 0);
    for(int i = 0; i <= mid; ++i) w[par[T[i]]] = 1;
    if(ask(w) > val){
      res = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }
  answer(0, T[res]);
}

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