제출 #483502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483502		Misuki	Race (IOI11_race)	C++17	21 / 100	3064 ms	12224 KiB

race

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int SIZE = 200000;
int n, k, ans = INT_MAX;
vector<pii> G[SIZE];
pii dis[SIZE];

int BFS(int S) {
  fill(dis, dis + n, make_pair(INT_MAX, INT_MAX));
  queue<int> q; //len, cost
  q.push(S);
  dis[S] = make_pair(0, 0);
  
  while(!q.empty()) {
    int now = q.front(); q.pop();
    int len = dis[now].first, cost = dis[now].second;
    for(auto [X, C] : G[now]) {
      if (dis[X].first == INT_MAX) {
        dis[X] = make_pair(len + 1, cost + C);
        q.push(X);
      }
    }
  }

  int tmp = INT_MAX;
  for(int i = 0; i < n; i++)
    if (dis[i].second == k)
      tmp = min(tmp, dis[i].first);
  return tmp;
}

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(make_pair(H[i][1], L[i]));
    G[H[i][1]].emplace_back(make_pair(H[i][0], L[i]));
  }

  for(int i = 0; i < N; i++)
    ans = min(ans, BFS(i));
  return ans == INT_MAX ? -1 : ans;
}
/*
int A[SIZE - 1][2], B[SIZE - 1];
int main() {
  int a, b; cin >> a >> b;
  for(int i = 0; i < a - 1; i++)
    cin >> A[i][0] >> A[i][1];
  for(int i = 0; i < a - 1; i++)
    cin >> B[i];
  cout << best_path(a, b, A, B) << '\n';
}
*/

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