Submission #151573

#	Time	Username	Problem	Language	Result	Execution time	Memory
151573		AlexPop28	Race (IOI11_race)	C++11	100 / 100	593 ms	87088 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int INF = (int)1e9;

struct MinMaxMerge {
  map<int, int> dist;
  int lazy_weight, lazy_edges;
  MinMaxMerge() : lazy_weight(0), lazy_edges(0) {
    dist.clear();
  }
};

struct Solver {
  Solver(int k_, const vector<vector<pair<int, int>>> &adj_) :
    n(adj_.size()), k(k_), adj(adj_) {}
  int n, k, ans = INF;
  vector<vector<pair<int, int>>> adj;

  void Merge(MinMaxMerge &curr, MinMaxMerge &him) {
    if (curr.dist.size() < him.dist.size()) {
      swap(curr, him);
    }
    for (auto &p : him.dist) {
      int real_weight = p.first + him.lazy_weight;
      int real_edges = p.second + him.lazy_edges;
      int search = k - real_weight - curr.lazy_weight;
      if (curr.dist.count(search)) {
        ans = min(ans, curr.dist[search] + curr.lazy_edges + real_edges);
      }
    }
    for (auto &p : him.dist) {
      int dist = p.first + him.lazy_weight - curr.lazy_weight;
      int edges = p.second + him.lazy_edges - curr.lazy_edges;
      if (curr.dist.count(dist)) {
        curr.dist[dist] = min(curr.dist[dist], edges);
      } else {
        curr.dist[dist] = edges;
      }
    }
  }

  MinMaxMerge DFS(int node, int parent) {
    MinMaxMerge curr;
    curr.dist[0] = 0;
    for (auto &p : adj[node]) if (p.first != parent) {
      auto him = DFS(p.first, node);
      him.lazy_weight += p.second;
      ++him.lazy_edges;
      Merge(curr, him);
    }
    return curr;
  }

  int Solve() {
    DFS(0, -1);
    return ans == INF ? -1 : ans;
  }
};

int best_path(int n, int k, int H[][2], int L[]) {
  vector<vector<pair<int, int>>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    adj[H[i][0]].emplace_back(H[i][1], L[i]);
    adj[H[i][1]].emplace_back(H[i][0], L[i]);
  }
  Solver solver(k, adj);
  return solver.Solve();
}

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