oj.uz

Submission #435719

# Submission time Handle Problem Language Result Execution time Memory
435719 2021-06-23T15:41:47 Z illyakr Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 4 ms 3276 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

vector<pair<int, int> > g[101010];
bool used[101010];
int ans[101010];
bool cn[101010];
int dfs(int v, int sum) {
    if (cn[v]) {
        ans[v] = 0;
        return 0;
    }
    if (used[v])return 1010101010;
    used[v] = true;

    int Mn1 = 1010101010;
    int Mn2 = 1010101010;
    for (auto [to, c] : g[v]) {
        if (used[to])continue;
        int gtn = dfs(to, sum + c);
        if (ans[to] + c < Mn1) {
            Mn2 = Mn1;
            Mn1 = gtn + c;
        } else if (gtn + c < Mn2) {
            Mn2 = gtn + c;
        }
    }
    if (ans[v] != -1) {
        if (ans[v] != Mn2)exit(1);
    }
    ans[v] = Mn2;
    used[v] = false;

    return Mn2;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for (int i = 0; i < M; i++) {
        g[R[i][0] + 1].push_back({R[i][1] + 1, L[i]});
        g[R[i][1] + 1].push_back({R[i][0] + 1, L[i]});
    }
    for (int i = 0; i < K; i++)
        cn[P[i] + 1] = true;
    memset(ans, -1, sizeof(ans));
    return dfs(1, 0);
}


/**
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14
*/

Compilation message

crocodile.cpp: In function 'int dfs(int, int)':
crocodile.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [to, c] : g[v]) {
      |               ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Runtime error 4 ms 3276 KB Execution failed because the return code was nonzero
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3052 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 3 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 2 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Runtime error 4 ms 3276 KB Execution failed because the return code was nonzero
10 Halted 0 ms 0 KB -