Submission #574201

#	Time	Username	Problem	Language	Result	Execution time	Memory
574201		keta_tsimakuridze	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	454 ms	63412 KiB

crocodile

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int maxn = 2e5 + 5, inf = 2e9 + 5;
vector<pii> V[maxn];
int d[maxn][2];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; i++) {
        int u = R[i][0], v = R[i][1];
        V[u].push_back({v, L[i]});
        V[v].push_back({u, L[i]});
    }
    for(int i = 0; i < N; i++) {
        d[i][0] = d[i][1] = inf;
    }
    priority_queue<pii, vector<pii>, greater<pii> > q;
    for(int i = 0; i < K; i++) d[P[i]][0] = d[P[i]][1] = 0, q.push({0, P[i]});

    while(q.size()) {
        int di = q.top().f, u = q.top().s;
        q.pop();
        if(di > d[u][1]) continue;
        for(int i = 0; i < V[u].size(); ++i) {
            int v = V[u][i].f;
            if(d[v][0] > di + V[u][i].s) {
                if(d[v][1] > d[v][0]) d[v][1] = d[v][0], q.push({d[v][1], v});
                d[v][0] = di + V[u][i].s;
            }
            else if(d[v][1]  > di + V[u][i].s) {
                d[v][1] = di + V[u][i].s;
                 q.push({d[v][1], v});
            }
        }
    } 
    return d[0][1];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0; i < V[u].size(); ++i) {
      |                        ~~^~~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11