Submission #1196620

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

crocodile

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

vector<vector<pair<int, int>>> g;
vector<int> dp, visited;
set<int> goated;

void dfs(int v, int par){
    if (goated.count(v) == 0){
        int mn = 1e9, second_mn = 1e9;
        visited[v] = 1;
        for (auto [u, w] : g[v]){
            if (u == par || visited[u]) 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;
            }
        }
        
        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);
    visited.resize(N);
    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++){
        goated.insert(E[i]);
        dp[E[i]] = 0;
    }
    
    dfs(0, -1);
    
    return dp[0];
}

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