Submission #682131

#	Time	Username	Problem	Language	Result	Execution time	Memory
682131		MattTheNub	Race (IOI11_race)	C++17	0 / 100	3031 ms	352 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

template <class T> using v = vector<T>;
using int2 = pair<int, int>;
using ll = long long;
using ll2 = pair<ll, ll>;

#define f first
#define s second
#define all(x) begin(x), end(x)

struct Paths {
  ll2 d = {0, 0};
  map<ll, ll> m;
};
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';

Paths dfs(v<v<int2>> &adj, int &ans, int k, int node, int prev) {
  Paths cur;

  // find all unions of paths
  v<Paths> paths;
  for (auto next : adj[node]) {
    if (next.f != prev) {
      paths.push_back(dfs(adj, ans, k, next.f, node));
    }
  }
  Paths halves;
  sort(all(paths), [](Paths &a, Paths &b) { return a.m.size() < b.m.size(); });
  for (int i = 0; i < paths.size(); i++) {
    if (paths[i].m.size() > halves.m.size()) {
      swap(paths[i], halves);
    }

    for (auto x : paths[i].m) {
      ll cost = x.f + paths[i].d.f;

      if (halves.m.count(k - cost - halves.d.f)) {
        ans = min(ans, (int)(x.s + paths[i].d.s +
                             halves.m[k - cost - halves.d.f] + halves.d.s));
      }
    }

    if (i != paths.size() - 1) {
      for (auto x : paths[i].m) {
        ll cost = x.f + paths[i].d.f;
        ll vx = x.s + paths[i].d.s;

        if (cost < k && vx < ans) {
          if (halves.m.count(cost - halves.d.f)) {
            halves.m[cost - halves.d.f] =
                min(halves.m[cost - halves.d.f], vx - halves.d.s);
          } else {
            halves.m[cost - halves.d.f] = vx - halves.d.s;
          }
        }
      }
    }
  }

  // construct new path set
  for (auto next : adj[node]) {
    if (next.f != prev) {
      Paths p = dfs(adj, ans, k, next.f, node);

      if (p.m.size() > cur.m.size()) {
        swap(p, cur);
        cur.d.f += next.s;
        cur.d.s += 1;
      } else {
        p.d.f += next.s;
        p.d.s += 1;
      }

      for (auto x : p.m) {
        ll cost = x.f + p.d.f;
        // dbg(cost);
        ll vx = x.s + p.d.s;
        if (cost < k && vx < ans) {
          if (cur.m.count(cost - cur.d.f)) {
            cur.m[cost - cur.d.f] = min(cur.m[cost], vx - cur.d.s);
          } else {
            cur.m[cost - cur.d.f] = vx - cur.d.s;
          }
        }
      }

      cur.m[next.s - cur.d.f] = 1 - cur.d.s;
    }
  }

  if (cur.m.count(k - cur.d.f)) {
    // dbg(node);
    // dbg(cur.m[k - cur.d.f]);
    ans = min(ans, (int)(cur.m[k - cur.d.f] + cur.d.s));
  }

  return cur;
}

int best_path(int N, int K, int H[][2], int L[]) {
  int ans = INT_MAX;
  v<v<int2>> adj(N);
  for (int i = 0; i < N - 1; i++) {
    adj[H[i][0]].push_back({H[i][1], L[i]});
    adj[H[i][1]].push_back({H[i][0], L[i]});
  }

  Paths p = dfs(adj, ans, K, 0, -1);

  if (ans == INT_MAX)
    ans = -1;

  return ans;
}

Compilation message (stderr)

race.cpp: In function 'Paths dfs(v<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >&, int&, int, int, int)':
race.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Paths, std::allocator<Paths> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int i = 0; i < paths.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
race.cpp:46:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Paths, std::allocator<Paths> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if (i != paths.size() - 1) {
      |         ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57