Submission #1219906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219906		SpyrosAliv	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	1 ms	584 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
vector<vector<pair<int, int>>> tree;
vector<ll> dp;

void dfs(int node, int p = 0) {
    for (auto [nxt, w]: tree[node]) {
        if (nxt == p) continue;
        dfs(nxt, node);
    }
    vector<ll> chDp;
    for (auto [nxt, w]: tree[node]) if (nxt != p) chDp.push_back(dp[nxt] + w);
    if (chDp.empty()) return;
    sort(chDp.begin(), chDp.end());
    dp[node] = chDp[1];
}

int travel_plan(int N, int M, int r[][2], int l[], int k, int p[]) {
    n = N;
    tree.clear();
    tree.resize(n);
    for (int i = 0; i < n-1; i++) {
        int u = r[i][0];
        int v = r[i][1];
        int w = l[i];
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }
    dp.assign(n, 0);
    dfs(0);
    return (int)dp[0];
}

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