Submission #743771

#	Time	Username	Problem	Language	Result	Execution time	Memory
743771		rominanafu	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	571 ms	66640 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11