Submission #468131

#	Time	Username	Problem	Language	Result	Execution time	Memory
468131		aryan12	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	3 ms	2764 KiB

crocodile

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

const int MAXN = 1e5 + 5, INF = 1e9 + 5;
vector<pair<int, int> > g[MAXN];
set<int> exit_chambers;
int dp[MAXN];
bool vis[MAXN];

void dfs(int node, int par) {
    if(dp[node] != -1 || vis[node]) {
        return;
    }
    if(exit_chambers.count(node)) {
        dp[node] = 0;
        return;
    }
    vis[node] = true;
    int max_val = INF, second_max_val = INF;
    for(int i = 0; i < g[node].size(); i++) {
        dfs(g[node][i].first, node);
        if(dp[g[node][i].first] == -1) {
            continue;
        }
        if(max_val > dp[g[node][i].first] + g[node][i].second) {
            second_max_val = max_val;
            max_val = dp[g[node][i].first] + g[node][i].second;
        }
        else if(second_max_val > dp[g[node][i].first] + g[node][i].second) {
            second_max_val = dp[g[node][i].first] + g[node][i].second;
        }
    }
    dp[node] = second_max_val;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{   
    for(int i = 0; i < N + 5; i++) {
        dp[i] = -1;
        vis[i] = false;
    }
    for(int i = 0; i < M; i++) {
        g[R[i][0]].push_back(make_pair(R[i][1], L[i]));
        g[R[i][1]].push_back(make_pair(R[i][0], L[i]));
    }
    for(int i = 0; i < K; i++) {
        exit_chambers.insert(P[i]);
    }
    dfs(0, -1);
    return dp[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'void dfs(int, int)':
crocodile.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

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