Submission #1265327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265327		canhnam357	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	188 ms	327680 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[R[i][0]].emplace_back(R[i][1], L[i]);
        adj[R[i][1]].emplace_back(R[i][0], L[i]);
    }
    vector<int> dp(N, INT_MAX);
    function<void(int, int)> dfs = [&](int u, int p) {
        int fi = INT_MAX, se = INT_MAX;
        for (auto [v, w] : adj[u]) {
            if (v == p) continue;
            dfs(v, u);
            if (w + dp[v] < fi) {
                se = fi;
                fi = w + dp[v];
            }
            else if (w + dp[v] < se) {
                se = w + dp[v];
            }
        }
        dp[u] = se;
        if (dp[u] == INT_MAX) dp[u] = 0;
    };
    dfs(0, 0);
    return dp[0];
}

// int main() {
//     int N, M, K;
//     cin >> N >> M >> K;
//     int R[M][2], L[M], P[K];
//     for (int i = 0; i < M; i++) {
//         cin >> R[i][0] >> R[i][1] >> L[i];
//     }
//     for (int i = 0; i < K; i++) cin >> P[i];
//     cout << travel_plan(N, M, R, L, K, P);
// }

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11