oj.uz

Submission #419462

# Submission time Handle Problem Language Result Execution time Memory
419462 2021-06-07T07:04:38 Z snasibov05 Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 2 ms 588 KB 
#include "crocodile.h"
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ll, ll>
#define f first;
#define s second;
#define oo 1000000000000000000ll

vector<vector<pii>> ed;
vector<bool> ext;
vector<int> visited;
vector<ll> res;

ll dfs(int v){
    visited[v] = 1;
    vector<ll> cur;
    for (auto [x, l] : ed[v]){
        if (visited[x] == 1) continue;

        if (ext[x]) cur.pb(l);
        else if (visited[x] == 2) cur.pb(res[x] + l);
        else cur.pb(dfs(x) + l);
    }
    visited[v] = 2;
    sort(cur.begin(), cur.end());
    if (cur.size() <= 1) return res[v] = oo;
    return res[v] = cur[1];
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){

    ed.resize(n);
    ext.resize(n);
    visited.resize(n);
    res.resize(n);

    for (int i = 0; i < m; ++i) {
        ed[r[i][0]].pb({r[i][1], l[i]});
        ed[r[i][1]].pb({r[i][0], l[i]});
    }

    for (int i = 0; i < k; ++i) {
        ext[p[i]] = true;
    }

    int ans = (int)dfs(0);

    return ans;

}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Halted 0 ms 0 KB -