Submission #993616

#	Time	Username	Problem	Language	Result	Execution time	Memory
993616		poqmen	Highway Tolls (IOI18_highway)	C++14	51 / 100	257 ms	262144 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
using namespace std;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
  vector<vector<int>> adj(n);
  int m = u.size();
  for (int i = 0; i < m; ++i)
    adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
  vector<int> in(n);
  vector<int> dfs_ord;
  int s = -1;
  int t = 0;
  function<void(int, int)> dfs = [&](int node, int par) {
    dfs_ord.push_back(node);
    in[node] = t++;
    for (auto v : adj[node]) {
      if (v == par) continue;
      if (v == s) continue;
      dfs(v, node);
    }
  };
  dfs(0, -1);
  // subgraph w. only verts with in[i] < t
  // t = tl -> len ineq.
  // t = th -> len eq.
  int tl = 0, th = t;
  vector<int> hl(m, 0);
  int64_t req_d = ask(hl);
  while (tl + 1 < th) {
    int tm = (tl + th) / 2;
    for (int i = 0; i < m; ++i) {
      hl[i] = in[u[i]] >= tm || in[v[i]] >= tm;
    }
    if (ask(hl) == req_d) {
      th = tm;
    } else {
      tl = tm;
    }
  }
  s = dfs_ord[tl];
  dfs_ord.clear();
  in.assign(n, -1);
  t = 0;
  dfs(s, -1);
  hl.assign(m, 1);
  tl = 0, th = t;
  req_d = ask(hl);
  while (tl + 1 < th) {
    int tm = (tl + th) / 2;
    for (int i = 0; i < m; ++i) {
      hl[i] = in[u[i]] < tm && in[v[i]] < tm;
    }
    if (ask(hl) == req_d) {
      th = tm;
    } else {
      tl = tm;
    }
  }
  t = dfs_ord[tl];
  answer(s, t);
}

#ifndef EVAL
#include "grader.cpp"
#endif

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