Submission #24191

#	Time	Username	Problem	Language	Result	Execution time	Memory
24191		Nirjhor	Race (IOI11_race)	C++14	0 / 100	6 ms	5112 KiB

race

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

using namespace std;

typedef long long ll;
typedef pair <int, ll> edge;

#define x first
#define y second

const int N = 200010;
const int INF = 1e9 + 10;

vector <edge> g[N];
int n, k, ans = INF;

void dfs (int u, int from, map <ll, int> &f) {
  for (edge e : g[u]) {
    int v = e.x; 
    ll w = e.y;
    if (v == from) continue;
    map <ll, int> t;
    t[0] = 0;
    dfs(v, u, t);
    if (t.size() > f.size()) {
      f.swap(t);
    }
    for (auto it : t) {
      ll more = k - it.x - w;
      if (more == 0) {
        ans = min(ans, it.y + 1);
      } else if (f.find(more) != f.end()) {
        ans = min(ans, it.y + f[more] + 1);
      }
    }
    for (auto it : t) {
      if (f.find(it.x + w) == f.end()) f[it.x + w] = INF;
      f[it.x + w] = min(f[it.x + w], it.y + 1);
    }
  }
}

int best_path (int N, int K, int H[][2], int L[]) {
  n = N, k = K;
  for (int i = 0; i < n - 1; ++i) {
    g[H[i][0]].emplace_back(H[i][1], L[i]);
    g[H[i][1]].emplace_back(H[i][0], L[i]);
  }
  map <ll, int> f;
  f[0] = 0;
  dfs(0, 0, f);
  if (ans >= INF / 2) ans = -1;
  return ans;
}

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