oj.uz

Submission #743771

# Submission time Handle Problem Language Result Execution time Memory
743771 2023-05-18T00:44:27 Z rominanafu Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 571 ms 66640 KB 
#include <bits/stdc++.h>
#define pii pair<int,int>
 
using namespace std;
typedef long long ll;
 
vector<pii > edge[100005];
pii tiempo[100005];
bool vis[100005];
priority_queue<pii > q;
 
void tiempo_min() {
    int costo, nodo, c;
    while (!q.empty()) {
        costo = q.top().first;
        nodo = q.top().second;
        q.pop();
        while(!q.empty() && vis[nodo]) {
            costo = q.top().first;
            nodo = q.top().second;
            q.pop();
        }
        if (vis[nodo]) /// poner vis[nodo]=true cuando tenga los dos caminos mínimos
            break;
        costo *= -1;
        if (tiempo[nodo].first == -1) {
            tiempo[nodo].first = costo;
            continue;
        }
        tiempo[nodo].second = costo;
        vis[nodo] = true;
        for(auto v:edge[nodo]) {
            if (vis[v.first])
                continue;
            c = costo + v.second;
            c *= -1;
            q.push({c, v.first});
        }
    }
}
 
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    memset(tiempo, -1, sizeof(tiempo));
    int a, b, t;
    for(int i=0; i<m; i++) {
        a = R[i][0];
        b = R[i][1];
        t = L[i];
        edge[a].push_back({b, t});
        edge[b].push_back({a, t});
    }
    for(int i=0; i<k; i++) {
        a = P[i];
        vis[a] = true;
        tiempo[a].first = 0;
        tiempo[a].second = 0;
        for(auto v:edge[a]) {
            q.push({v.second * (-1), v.first});
        }
    }
    tiempo_min();
    return tiempo[0].second;
}
 
/**
4 4 1
0 1 9
0 3 10
1 2 40
2 3 100
2
(-1)

9 9 5
0 1 1
0 2 4
1 3 6
1 4 2
2 5 3
2 6 8
6 5 100
6 7 40
6 8 1
3 4 5 7 8
(52)
**/

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:44:38: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   44 |     memset(tiempo, -1, sizeof(tiempo));
      |                                      ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from crocodile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 3 ms 3416 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 3 ms 3416 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 4 ms 3796 KB Output is correct
10 Correct 3 ms 3428 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 6 ms 4092 KB Output is correct
13 Correct 7 ms 4180 KB Output is correct
14 Correct 2 ms 3440 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 2 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 3 ms 3416 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 4 ms 3796 KB Output is correct
10 Correct 3 ms 3428 KB Output is correct
11 Correct 3 ms 3540 KB Output is correct
12 Correct 6 ms 4092 KB Output is correct
13 Correct 7 ms 4180 KB Output is correct
14 Correct 2 ms 3440 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 532 ms 64376 KB Output is correct
17 Correct 72 ms 13768 KB Output is correct
18 Correct 80 ms 15328 KB Output is correct
19 Correct 571 ms 66640 KB Output is correct
20 Correct 358 ms 58644 KB Output is correct
21 Correct 37 ms 8260 KB Output is correct
22 Correct 352 ms 46820 KB Output is correct