제출 #1191287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191287		GoBananas69	Race (IOI11_race)	C++20	21 / 100	3095 ms	8260 KiB

race

#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

typedef long long ll;

vector<vector<pair<int, int>>> adj;
vector<bool> vis;
vector<int> dist, depth;

void dfs(int u) {
    vis[u] = true;
    for (auto &p : adj[u]) {
        int w = p.second;
        int v = p.first;
        if (!vis[v]) {
            dist[v] = dist[u] + w;
            depth[v] = depth[u] + 1;
            dfs(v);
        }
    }
}

int best_path(int n_, int k_, int edges_[][2], int length_[]) {
    int n = n_, k = k_;
    adj.resize(n);
    vis.resize(n, false);
    dist.resize(n);
    depth.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u = edges_[i][0], v = edges_[i][1], w = length_[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    int res = 1e9;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dist[j] = 0;
            depth[j] = 0;
            vis[j] = false;
        }
        depth[i] = 0;
        dist[i] = 0;
        dfs(i);
        for (int j = 0; j < n; ++j) {
            if (dist[j] == k) {
                res = min(res, depth[j]);
            }
        }
    }
    return (res == 1e9 ? -1 : res);
}

// int main() {
//     int h[10][2] = {
//         {0, 1},
//         {0, 2},
//         {2, 3},
//         {3, 4},
//         {4, 5},
//         {0, 6},
//         {6, 7},
//         {6, 8},
//         {8, 9},
//         {8, 10}};
//     int l[10] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
//     cout << best_path(11, 12, h, l);
//     return 0;
// }

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