제출 #914464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914464		Isaac_Q	경주 (Race) (IOI11_race)	C++14	21 / 100	3025 ms	12160 KiB

race

#include <bits/stdc++.h>
#include<vector>
#define rep(i, n) for(int i=0; i<n; i++)
#define pii pair<int, ll>
#define ll long long
using namespace std;
ll TARGET;
const int INF = 1e9;
int BEST;
 
vector<vector<pii>> graph;
 
void DFS(int p, int node, ll w, int lenght){
    if(w > TARGET) return;
    if(w == TARGET) BEST = min(BEST,lenght);

    for(auto &e: graph[node])
    {
        if(e.first == p) continue;

        DFS(node, e.first, w + e.second, lenght + 1);
    }
}
 
 
int best_path(int N, int K, int H[][2], int L[]){
    graph.assign(N,vector<pii>{});
    TARGET = K;
    int a, b, l;
    for(int i=0; i<N-1; i++)
    {
        a = H[i][0]; b = H[i][1]; l = L[i];
        graph[a].push_back({b,l});
        graph[b].push_back({a,l});
    }

    BEST = INF;

    for(int i=0; i<N-1; i++) DFS(-1,i,0,0);

    if(BEST == INF) return -1;
    return BEST;
}

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