oj.uz

Submission #927253

# Submission time Handle Problem Language Result Execution time Memory
927253 2024-02-14T14:08:45 Z hengliao Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 622 ms 64272 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define vllll vector<vector<ll, ll>>
#define debug(...) cout<<" [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "<<'\n';
typedef long long ll;

const int inf=1e9+5;

const int mxN=1e5+5;
vector<pair<int, int>> adj[mxN];
int dis[mxN];
bool done[mxN];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    memset(done, 0, sizeof(done));
    priority_queue<pair<int, int>> pq;
    for(int i=0;i<n;i++){
        dis[i]=inf;
    }
    for(int i=0;i<m;i++){
        adj[r[i][0]].pb({r[i][1], l[i]});
        adj[r[i][1]].pb({r[i][0], l[i]});
    }
    for(int i=0;i<k;i++){
        dis[p[i]]=0;
        pq.push({0, p[i]});
    }
    while(!pq.empty()){
        pair<int, int> cur=pq.top(); pq.pop();
        if(dis[cur.S]<inf && cur.F!=0) continue;
        if(!done[cur.S] && cur.F!=0){
            done[cur.S]=1;
            continue;
        }
        dis[cur.S]=min(-cur.F, dis[cur.S]);
        for(auto it:adj[cur.S]){
            pq.push({-(-cur.F+it.S), it.F});
        }
    }

    return dis[0];
}

/*test case


*/

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 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 6588 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6748 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 1 ms 6488 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 6588 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 6 ms 7260 KB Output is correct
13 Correct 6 ms 7360 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 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 6588 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 6 ms 7260 KB Output is correct
13 Correct 6 ms 7360 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 579 ms 60964 KB Output is correct
17 Correct 59 ms 13396 KB Output is correct
18 Correct 81 ms 14672 KB Output is correct
19 Correct 622 ms 64272 KB Output is correct
20 Correct 434 ms 58916 KB Output is correct
21 Correct 33 ms 9044 KB Output is correct
22 Correct 462 ms 35900 KB Output is correct