Submission #1237262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237262		dosts	Highway Tolls (IOI18_highway)	C++20	51 / 100	301 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 90001, inf = 2e9;

vector<pii> edges[LIM];
vi tin(LIM),tout(LIM),par(LIM);
int timer = 0;
int up[LIM][17];
vi edgs,edgs2;
void dfs(int node,int p) {
  tin[node] = timer++;
  par[node] = p;
  up[node][0] = p;
  for (int i=1;i<17;i++) {
    up[node][i] = up[up[node][i-1]][i-1];
  }
  for (auto it : edges[node]) {
    if (it.ff == p) continue;
    edgs2.push_back(it.ss);
    dfs(it.ff,node);
    edgs.push_back(it.ss);
  }
  tout[node] = timer++;
}

int maxtin(int a,int b) {
  if (tin[a] >= tin[b]) return a;
  return b;
}
bool anc(int a,int b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lift(int a,int k) {
  for (int i= 16;i>=0;i--) {
    if (k&(1<<i)) a = up[a][i];
  }
  return a;
}
void find_pair(signed N, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
  int M = U.size();
  vector<pii> edg;
  for (int i = 0;i<M;i++) {
    edges[U[i]].push_back({V[i],i});
    edges[V[i]].push_back({U[i],i});
    edg.push_back({U[i],V[i]});
  }
  dfs(0,0);
  int l = 1;
  int r = M;
  int init = ask(vector<int32_t>(M,0));
  int initoll = init;
  int L,R;
  while (l<=r) {
    vector<int32_t> q(M,0);
    int m = (l+r) >> 1;
    for (int j = 0;j<m;j++) q[edgs[j]] = 1;
    int toll = ask(q);
    int pass = (toll-init)/(B-A);
    if (pass) r = m-1;
    else l = m+1;
  }
  L = l;
  l = 1;
  r = M;
  while (l<=r) {
    vector<int32_t> q(M,0);
    int m = (l+r) >> 1;
    for (int j = M-1;j >= m-1;j--) q[edgs2[j]] = 1;
    int toll = ask(q);
    int pass = (toll-init)/(B-A);
    if (pass) l = m+1;
    else r = m-1;
  }
  R = r;
  int alt1 = maxtin(edg[edgs[L-1]].ff,edg[edgs[L-1]].ss);
  int alt2 = maxtin(edg[edgs2[R-1]].ff,edg[edgs2[R-1]].ss);
  if (anc(alt1,alt2)) alt1 = lift(alt2,initoll/A);
  answer(alt1,alt2);
}

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