Submission #597793

#	Time	Username	Problem	Language	Result	Execution time	Memory
597793		TimDee	Highway Tolls (IOI18_highway)	C++14	51 / 100	195 ms	13220 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
  int m=u.size();
  vector<int> scuza(m,1); vector<int> paiu;
  ll dist = ask(scuza)/b;
  vector<vector<pair<int,int>>> adj(n);
  for (int i=0; i<m; ++i) {
    adj[u[i]].push_back({v[i],i});
    adj[v[i]].push_back({u[i],i});
  }
  vector<int> vis(n,0), d(n,0); vis[0]=1;
  vector<int> edges;
  queue<int> q; q.push(0);
  while (!q.empty()) {
    int u=q.front(); q.pop();
    for (auto it:adj[u]) {
      int v=it.first;
      if (!vis[v]) {
        vis[v]=1;
        d[v]=d[u]+1;
        edges.push_back(it.second);
        q.push(v);
      }
    }
  }
  int l=0, r=edges.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    paiu=scuza;
    for (int i=0; i<=mid; ++i) paiu[edges[i]]=0;
    ll x = ask(paiu);
    if (x<1ll*dist*b) r=mid;
    else l=mid+1;
  }
  int bgn;
  if (d[u[edges[r]]]<d[v[edges[r]]]) bgn = u[edges[r]];
  else bgn = v[edges[r]];
  d.assign(n,0);
  vis.assign(n,0);
  vis[bgn]=1;
  q.push(bgn);
  edges.clear();
  while (!q.empty()) {
    int u=q.front(); q.pop();
    for (auto it:adj[u]) {
      int v=it.first;
      if (!vis[v]) {
        vis[v]=1;
        d[v]=d[u]+1;
        edges.push_back(it.second);
        q.push(v);
      }
    }
  }
  l=0,r=edges.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    paiu=scuza;
    for (int i=0; i<=mid; ++i) paiu[edges[i]]=0;
    ll x = ask(paiu);
    if (x>1ll*dist*a) l=mid+1;
    else r=mid;
  }
  int s = d[u[edges[r]]]>d[v[edges[r]]] ? u[edges[r]] : v[edges[r]];
  d.assign(n,0);
  vis.assign(n,0);
  vis[s]=1;
  q.push(s);
  vector<vector<int>>D(n);
  while (!q.empty()) {
    int u=q.front(); q.pop();
    for (auto it:adj[u]) {
      int v=it.first;
      if (!vis[v]) {
        vis[v]=1;
        d[v]=d[u]+1;
        D[d[v]].push_back(v);
        q.push(v);
      }
    }
  }
  vector<int>amog=D[dist];
  l=0, r=amog.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    paiu=scuza;
    for (int i=0; i<=mid; ++i) for (auto it:adj[amog[i]]) {
      int v=it.first;
      if (d[v]==d[amog[i]]-1) paiu[it.second]=0;
    }
    ll x = ask(paiu);
    if (x<1ll*dist*b) r=mid;
    else l=mid+1;
  } //cout<<s<<' '<<amog[r]<<'\n';
  answer(s,amog[r]);
}

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