Submission #1196608

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

crocodile

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

vector<vector<pair<int, int>>> g;
vector<int> dp;

void dfs(int v, int par){
    
    int mn = 1e9, second_mn = 1e9;
    for (auto [u, w] : g[v]){
        if (u == par) continue;
        
        dfs(u, v);
        int path = dp[u] + w;
        
        if (path < mn){
            second_mn = mn;
            mn = path;
        }else if (path == mn){
            second_mn = path;
        }else if (path < second_mn){
            second_mn = path;
        }
    }
    
    if (dp[v] != 0) dp[v] = second_mn;
    
    //cout << v << ' ' << par << ' ' << dp[v] << endl;
}

int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]){
    g.resize(N);
    dp.resize(N, 1e9);
    for (int i = 0; i < M; i++){
        int a = R[i][0], b = R[i][1], c = W[i];
        
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    
    for (int i = 0; i < K; i++){
        dp[E[i]] = 0;
    }
    
    dfs(0, -1);
    
    return dp[0];
}

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