Submission #423810

#	Time	Username	Problem	Language	Result	Execution time	Memory
423810		Tangent	Highway Tolls (IOI18_highway)	C++17	18 / 100	727 ms	216500 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

pii solve(int N, std::vector<int> &U, std::vector<int> &V, int A, int B, vii &verts, vii &edges) {
  int M = U.size();
  vvpii adj(N);
  forin(i, edges) {
    adj[U[i]].emplace_back(V[i], i);
    adj[V[i]].emplace_back(U[i], i);
  }

  vii depth(N, -1), parent(N), pedge(N);
  depth[verts[0]] = 0;

  function<void(int)> dfs;
  dfs = [&](int x) {
    forin(y, adj[x]) {
      if (depth[y.first] == -1) {
        depth[y.first] = depth[x] + 1;
        parent[y.first] = x;
        pedge[y.first] = y.second;
        dfs(y.first);
      }
    }
  };
  dfs(verts[0]);
  int deepest = verts[0];
  forin(i, verts) {
    if (depth[i] > depth[deepest]) {
      deepest = i;
    }
  }
  depth.assign(N, -1);
  depth[deepest] = 0;
  parent.assign(N, -1);
  dfs(deepest);
  int deepest2 = verts[0];
  forin(i, verts) {
    if (depth[i] > depth[deepest2]) {
      deepest2 = i;
    }
  }
  vii diameter = {deepest2}, dedges;
  vii ondiam(N);
  ondiam[deepest2] = 1;
  while (diameter.back() != deepest) {
    dedges.emplace_back(pedge[diameter.back()]);
    diameter.emplace_back(parent[diameter.back()]);
    ondiam[diameter.back()] = 1;
  }

  vii query(M);
  ll dist = ask(query) / A;
  forin(dedge, dedges) {
    query[dedge] = 1;
  }
  ll ddist = (ask(query) - (dist * A)) / (B - A);
  forin(dedge, dedges) {
    query[dedge] = 0;
  }

  if (ddist == 0) {
    deque<vii> groups(diameter.size()), groupse(diameter.size());
    function<void(int, int)> dfs2;
    dfs2 = [&](int x, int group) {
      groups[group].emplace_back(x);
      forin(y, adj[x]) {
        if (y.first != parent[x]) {
          if (ondiam[y.first]) {
            dfs2(y.first, group + 1);
          } else {
            groupse[group].emplace_back(y.second);
            dfs2(y.first, group);
          }
        }
      }
    };
    dfs2(deepest, 0);

    while (groups.size() > 1) {
      vii query2(M);
      rep(i, groups.size() / 2) {
        forin(edge, groupse[i]) {
          query2[edge] = 1;
        }
      }
      if (ask(query2) > dist * A) {
        groups.resize(groups.size() / 2);
        groupse.resize(groupse.size() / 2);
      } else {
        int x = groups.size() / 2;
        rep(i, x) {
          groups.pop_front();
          groupse.pop_front();
        }
      }
    }
    auto &group = groups[0];
    auto &groupe = groupse[0];

    return solve(N, U, V, A, B, group, groupe);
  }

  int lo = 0, hi = diameter.size() - 1 - ddist;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    for (int x = mid; x >= 0; x-= ddist) {
      query[dedges[x]] = 1;
    }
    if (ask(query) > dist * A) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
    for (int x = mid; x >= 0; x-= ddist) {
      query[dedges[x]] = 0;
    }
  }

  lo = diameter[lo];
  hi = diameter[hi + ddist];
  vii lodepth(N), hidepth(N);
  int s, t;
  deque<int> q = {lo};
  while (!q.empty()) {
    int x = q.front();
    q.pop_front();
    forin(y, adj[x]) {
      if (y.first != parent[x] && !ondiam[y.first]) {
        q.emplace_back(y.first);
        query[y.second] = 1;
        lodepth[y.first] = lodepth[x] + 1;
      }
    }
  }

  ll lodist = (ask(query) - (dist * A)) / (B - A);
  query.assign(M, 0);
  if (lodist == 0) {
    s = lo;
  } else {
    vii cand;
    rep(i, N) {
      if (lodepth[i] == lodist) {
        cand.emplace_back(i);
      }
    }
    while (cand.size() > 1) {
      vii query2(M);
      rep(i, cand.size() / 2) {
        query2[pedge[cand[i]]] = 1;
      }
      if (ask(query2) > dist * A) {
        cand.resize(cand.size() / 2);
      } else {
        ffor(i, cand.size() / 2, cand.size()) {
          cand[i - (cand.size() / 2)] = cand[i]; 
        }
        cand.resize(cand.size() - (cand.size() / 2));
      }
    }
    s = cand[0];
  }

  q = {hi};
  while (!q.empty()) {
    int x = q.front();
    q.pop_front();
    forin(y, adj[x]) {
      if (y.first != parent[x] && !ondiam[y.first]) {
        q.emplace_back(y.first);
        query[y.second] = 1;
        hidepth[y.first] = hidepth[x] + 1;
      }
    }
  }

  ll hidist = (ask(query) - (dist * A)) / (B - A);
  if (hidist == 0) {
    t = hi;
  } else {
    vii cand;
    rep(i, N) {
      if (hidepth[i] == hidist) {
        cand.emplace_back(i);
      }
    }
    while (cand.size() > 1) {
      vii query2(M);
      rep(i, cand.size() / 2) {
        query2[pedge[cand[i]]] = 1;
      }
      if (ask(query2) > dist * A) {
        cand.resize(cand.size() / 2);
      } else {
        ffor(i, cand.size() / 2, cand.size()) {
          cand[i - (cand.size() / 2)] = cand[i]; 
        }
        cand.resize(cand.size() - (cand.size() / 2));
      }
    }
    t = cand[0];
  }
  
  return {s, t};
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  vii verts, edges;
  rep(i, N) {
    verts.emplace_back(i);
  }
  rep(i, U.size()) {
    edges.emplace_back(i);
  }
  pii res = solve(N, U, V, A, B, verts, edges);
  answer(res.first, res.second);
}

Compilation message (stderr)

highway.cpp: In function 'pii solve(int, std::vector<int>&, std::vector<int>&, int, int, vii&, vii&)':
highway.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::deque<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
highway.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
highway.cpp:101:7: note: in expansion of macro 'rep'
  101 |       rep(i, groups.size() / 2) {
      |       ^~~
highway.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
highway.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
highway.cpp:169:7: note: in expansion of macro 'rep'
  169 |       rep(i, cand.size() / 2) {
      |       ^~~
highway.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
......
  175 |         ffor(i, cand.size() / 2, cand.size()) {
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:175:9: note: in expansion of macro 'ffor'
  175 |         ffor(i, cand.size() / 2, cand.size()) {
      |         ^~~~
highway.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
highway.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
highway.cpp:209:7: note: in expansion of macro 'rep'
  209 |       rep(i, cand.size() / 2) {
      |       ^~~
highway.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
......
  215 |         ffor(i, cand.size() / 2, cand.size()) {
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:215:9: note: in expansion of macro 'ffor'
  215 |         ffor(i, cand.size() / 2, cand.size()) {
      |         ^~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
highway.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
highway.cpp:232:3: note: in expansion of macro 'rep'
  232 |   rep(i, U.size()) {
      |   ^~~

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