제출 #910039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
910039		vjudge1	경주 (Race) (IOI11_race)	C++17	21 / 100	3063 ms	13504 KiB

race

#include <bits/stdc++.h>

//Debug
#define DEBUG_ON false
#define DBG(x) if(DEBUG_ON) cout << "Line(" << __LINE__ << ") -> " << #x << " = " << (x) << "\n";

//Macros
#define rep(i, n) for(int i=0; i<n; i++)
#define pii pair<int, ll>

typedef long long ll;

using namespace std;

//==================================
//GLOBALS
ll TARGET;
const int INF = 1e9;
int BEST;

vector<vector<pii>> graph;

//==================================

void DFS(int p, int node, ll w, int lenght){
    //Check
    if(w > TARGET) return;
    if(w == TARGET) BEST = min(BEST, lenght);

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

        DFS(node, v.first, v.second + w, lenght + 1);
    }
}


int best_path(int N, int K, int H[][2], int L[]){
    //Connect graph
    graph.assign(N, vector<pii>{});

    int a, b;
    ll w;
    rep(i, N-1){
        a= H[i][0], b= H[i][1], w= L[i];
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }

    //Solve
    BEST = INF;
    TARGET = K;
    rep(i, N)
        DFS(-1, i, 0, 0);
    
    return (BEST != INF) ? BEST : -1;
}


//==================================

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