Submission #423783

#	Time	Username	Problem	Language	Result	Execution time	Memory
423783		Tangent	Highway Tolls (IOI18_highway)	C++17	6 / 100	228 ms	16980 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, function<ll(vii&)> ask2) {
  int M = U.size();
  vvpii adj(N);
  rep(i, M) {
    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[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(0);
  int deepest = 0;
  rep(i, N) {
    if (depth[i] > depth[deepest]) {
      deepest = i;
    }
  }
  depth.assign(N, -1);
  depth[deepest] = 0;
  parent.assign(N, -1);
  dfs(deepest);
  int deepest2 = 0;
  rep(i, N) {
    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 = ask2(query) / A;
  forin(dedge, dedges) {
    query[dedge] = 1;
  }
  ll ddist = (ask2(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 (ask2(query2) > dist * A) {
        groups.resize(groups.size() / 2);
        groupse.resize(groupse.size() / 2);
      } else {
        int x = groups.size() - (groups.size() / 2);
        rep(i, x) {
          groups.pop_front();
          groupse.pop_front();
        }
      }
    }
    auto &group = groups[0];
    auto &groupe = groupse[0];
    vii label(N);
    rep(i, group.size()) {
      label[group[i]] = i;
    }
    vii NU, NV;
    forin(e, groupe) {
      NU.emplace_back(label[U[e]]);
      NV.emplace_back(label[V[e]]);
    }

    function<ll(vii&)> nask = [&] (vii &w) {
      vii query(M);
      rep(i, w.size()) {
        query[groupe[i]] = w[i];
      }
      return ask2(query);
    };

    pii nres = solve(group.size(), NU, NV, A, B, nask);
    return {group[nres.first], group[nres.second]};
  }

  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 (ask2(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 = (ask2(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 (ask2(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 = (ask2(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 (ask2(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) {
  pii res = solve(N, U, V, A, B, ask);
  answer(res.first, res.second);
}

Compilation message (stderr)

highway.cpp: In function 'pii solve(int, std::vector<int>&, std::vector<int>&, int, int, std::function<long long int(std::vector<int>&)>)':
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:120:5: note: in expansion of macro 'rep'
  120 |     rep(i, group.size()) {
      |     ^~~
highway.cpp: In lambda function:
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:131:7: note: in expansion of macro 'rep'
  131 |       rep(i, w.size()) {
      |       ^~~
highway.cpp: In function 'pii solve(int, std::vector<int>&, std::vector<int>&, int, int, std::function<long long int(std::vector<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:187:7: note: in expansion of macro 'rep'
  187 |       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++)
......
  193 |         ffor(i, cand.size() / 2, cand.size()) {
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:193:9: note: in expansion of macro 'ffor'
  193 |         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:227:7: note: in expansion of macro 'rep'
  227 |       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++)
......
  233 |         ffor(i, cand.size() / 2, cand.size()) {
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:233:9: note: in expansion of macro 'ffor'
  233 |         ffor(i, cand.size() / 2, cand.size()) {
      |         ^~~~

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