oj.uz

Submission #412140

# Submission time Handle Problem Language Result Execution time Memory
412140 2021-05-26T14:37:47 Z A_D Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1194 ms 100696 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define LL long long
#define ii pair<LL,LL>
#define F first
#define S second
using namespace std;
const int NN=1e5+100;
const int INF=1e18;
vector<ii> g[NN];
LL dp[NN];
priority_queue<LL,vector<LL>,greater<LL>> vec[NN];
priority_queue<ii,vector<ii>,greater<ii>> q;
void dijkstra()
{
    while(q.empty()==0){
        LL w=q.top().F;
        LL u=q.top().S;
        q.pop();
        if(w>dp[u])continue;
        for(auto x:g[u]){
            vec[x.F].push(x.S+dp[u]);
            LL v=vec[x.F].top();
            vec[x.F].pop();
            LL v2=vec[x.F].top();
            if(vec[x.F].empty()==0){
                if(dp[x.F]>v2){
                    dp[x.F]=v2;
                    q.push({v2,x.F});
                }
            }
            vec[x.F].push(v);
        }
    }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i=0;i<N;i++)dp[i]=INF;
    for(int i=0;i<K;i++){
        dp[P[i]]=0;
        q.push({0,P[i]});
    }
    for(int i=0;i<M;i++){
        LL u=R[i][0];
        LL v=R[i][1];
        LL w=L[i];
        g[u].push_back({v,w});
        g[v].push_back({u,w});
//        cout<<u<<" "<<v<<" "<<w<<endl;
    }
    dijkstra();
    LL ans=dp[0];
//    for(int i=0;i<N;i++)cout<<dp[i]<<" ";cout<<endl;
    return ans;
}


/*

5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4


5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3



*/

Compilation message

crocodile.cpp:9:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int INF=1e18;
      |               ^~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5852 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct
5 Correct 6 ms 5836 KB Output is correct
6 Correct 5 ms 5836 KB Output is correct
7 Correct 5 ms 5836 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Correct 6 ms 6220 KB Output is correct
10 Correct 4 ms 5832 KB Output is correct
11 Correct 7 ms 5904 KB Output is correct
12 Correct 11 ms 6572 KB Output is correct
13 Correct 8 ms 6724 KB Output is correct
14 Correct 4 ms 5808 KB Output is correct
15 Correct 5 ms 5964 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5708 KB Output is correct
3 Correct 4 ms 5852 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct
5 Correct 6 ms 5836 KB Output is correct
6 Correct 5 ms 5836 KB Output is correct
7 Correct 5 ms 5836 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Correct 6 ms 6220 KB Output is correct
10 Correct 4 ms 5832 KB Output is correct
11 Correct 7 ms 5904 KB Output is correct
12 Correct 11 ms 6572 KB Output is correct
13 Correct 8 ms 6724 KB Output is correct
14 Correct 4 ms 5808 KB Output is correct
15 Correct 5 ms 5964 KB Output is correct
16 Correct 1056 ms 89104 KB Output is correct
17 Correct 115 ms 24656 KB Output is correct
18 Correct 169 ms 27044 KB Output is correct
19 Correct 1194 ms 100696 KB Output is correct
20 Correct 518 ms 84380 KB Output is correct
21 Correct 60 ms 14868 KB Output is correct
22 Correct 508 ms 75352 KB Output is correct