Submission #682139

#	Time	Username	Problem	Language	Result	Execution time	Memory
682139		MattTheNub	Race (IOI11_race)	C++17	9 / 100	109 ms	23024 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};
  unordered_map<ll, ll> m;
};
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';

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

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

  for (auto i : adj[node]) {
    // dbg(node);
    if (i.f != prev) {
      for (auto j : adj[node]) {
        if (i.f > j.f && j.f != prev) {
          if (paths[i.f].m.size() < paths[j.f].m.size()) {
            swap(i, j);
          }

          for (auto x : paths[i.f].m) {
            ll cost = x.f + paths[i.f].d.f + i.s + j.s;
            ll vx = x.s + paths[i.f].d.s + 1;
            if (paths[j.f].m.count(k - cost - paths[j.f].d.f - i.s - j.s)) {
              ans = min(ans, (int)(x.s + paths[i.f].d.s +
                                   paths[j.f].m[k - cost - paths[j.f].d.f] +
                                   paths[j.f].d.s + 2));
            }
          }
        }
      }
    }
  }

  for (auto next : adj[node]) {
    if (next.f != prev) {
#define p paths[next.f]
      if (p.m.size() > cur.m.size()) {
        p.m.swap(cur.m);
        swap(p.d, cur.d);
        cur.d.f += next.s;
        cur.d.s += 1;
      } else {
        p.d.f += next.s;
        p.d.s += 1;
      }

      // dbg(node);
      // dbg(p.m.size());
      for (auto x : p.m) {
        ll cost = x.f + p.d.f;
        // dbg(cost);
        // dbg(cur.d.s);
        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;
      // dbg(cur.m[next.s - cur.d.f]);
    }
  }
  // dbg(cur.m.size());

  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));
  }

  paths[node] = {cur.d, move(cur.m)};
}

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]});
  }
  v<Paths> paths(N);
  dfs(adj, paths, ans, K, 0, -1);

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

  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(v<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >&, v<Paths>&, int&, int, int, int)':
race.cpp:42:16: warning: unused variable 'vx' [-Wunused-variable]
   42 |             ll vx = x.s + paths[i.f].d.s + 1;
      |                ^~

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