oj.uz

답안 #24191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24191 2017-06-01T11:23:47 Z Nirjhor 경주 (Race) (IOI11_race) C++14
0 / 100
 6 ms 5112 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -