oj.uz

Submission #434840

# Submission time Handle Problem Language Result Execution time Memory
434840 2021-06-21T23:21:12 Z illyakr Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 2000 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 sv = -1;
void dfs(int v, int sum) {
    if (used[v])return;
//    if (ans[v] != -1){ans[v] = max(ans[v], sum);return;}
    if (cn[v]) {
        ans[v] = 0;
        sv = sum;
        return;
    }
    used[v] = true;

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

    ans[v] = Mn2;
    used[v] = false;
}
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));
    dfs(1, 0);
    return ans[1];
}


/**
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 'void dfs(int, int)':
crocodile.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for (auto [to, c] : g[v]) {
      |               ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 3 ms 3020 KB Output is correct
5 Correct 4 ms 3020 KB Output is correct
6 Correct 2 ms 3020 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 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 3 ms 3020 KB Output is correct
5 Correct 4 ms 3020 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Execution timed out 2060 ms 3276 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3020 KB Output is correct
2 Correct 2 ms 3020 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 3 ms 3020 KB Output is correct
5 Correct 4 ms 3020 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Execution timed out 2060 ms 3276 KB Time limit exceeded
10 Halted 0 ms 0 KB -