oj.uz

Submission #468129

# Submission time Handle Problem Language Result Execution time Memory
468129 2021-08-26T19:48:55 Z aryan12 Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 3 ms 2892 KB 
//#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const long long INF = 1e15;
vector<pair<int, int> > g[MAXN];
set<int> exit_chambers;
long long 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;
    long long max_val = INF, second_max_val = INF;
    for(int i = 0; i < g[node].size(); i++) {
        if(g[node][i].first != par) {
            dfs(g[node][i].first, node);
            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 (int)(dp[0]);
}

Compilation message

crocodile.cpp: In function 'void dfs(int, int)':
crocodile.cpp:22: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]
   22 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2804 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2804 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Incorrect 3 ms 2892 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 3 ms 2804 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Incorrect 3 ms 2892 KB Output isn't correct
10 Halted 0 ms 0 KB -