oj.uz

Submission #1025720

# Submission time Handle Problem Language Result Execution time Memory
1025720 2024-07-17T09:11:52 Z idas Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 409 ms 71312 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;

const int MxN=1e5+10, INF=1e9+10;
vector<pii> ad[MxN];
bool in[MxN];
int d[MxN];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    FOR(i, 0, m)
    {
        ad[r[i][0]].pb({r[i][1],l[i]});
        ad[r[i][1]].pb({r[i][0],l[i]});
    }

    FOR(i, 0, n) d[i]=-1;

    priority_queue<pii, vector<pii>, greater<pii>> q;
    FOR(i, 0, k)
    {
        q.push({0,p[i]});
        q.push({0,p[i]});
    }

    while(!q.empty()){
        int val=q.top().f, u=q.top().s; q.pop();

        if(in[u]) continue;

        if(d[u]==-1){
            d[u]=val;
            continue;
        }

        d[u]=val;
        in[u]=true;

        for(auto it : ad[u]){
            int x=it.f, w=it.s;
            if(in[x]) continue;

            int nd=min(INF, d[u]+w);
            q.push({nd,x});
        }
    }

    return d[0]==INF?-1:d[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6608 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 4 ms 7004 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6608 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 4 ms 7004 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 354 ms 69056 KB Output is correct
17 Correct 45 ms 16728 KB Output is correct
18 Correct 63 ms 18004 KB Output is correct
19 Correct 409 ms 71312 KB Output is correct
20 Correct 298 ms 62736 KB Output is correct
21 Correct 25 ms 10320 KB Output is correct
22 Correct 281 ms 49744 KB Output is correct