oj.uz

Submission #412119

# Submission time Handle Problem Language Result Execution time Memory
412119 2021-05-26T14:18:21 Z A_D Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 331 ms 35452 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=1e3+100;
const int INF=1e18;
vector<ii> g[NN];
LL dp[NN];
vector<LL> vec;
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;
    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;
    }
    int h=N;
    while(h--){
        for(int i=0;i<N;i++){
            vec.clear();
            for(auto x:g[i]){
                vec.push_back(dp[x.F]+x.S);
            }
            sort(vec.begin(),vec.end());
            if(vec.size()>1){
                dp[i]=min(dp[i],vec[1]);
            }
        }
    }
    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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 24 ms 436 KB Output is correct
6 Correct 13 ms 416 KB Output is correct
7 Correct 31 ms 332 KB Output is correct
8 Correct 27 ms 332 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 24 ms 436 KB Output is correct
6 Correct 13 ms 416 KB Output is correct
7 Correct 31 ms 332 KB Output is correct
8 Correct 27 ms 332 KB Output is correct
9 Correct 51 ms 748 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 18 ms 588 KB Output is correct
12 Correct 140 ms 972 KB Output is correct
13 Correct 56 ms 1156 KB Output is correct
14 Correct 4 ms 460 KB Output is correct
15 Correct 15 ms 460 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 24 ms 436 KB Output is correct
6 Correct 13 ms 416 KB Output is correct
7 Correct 31 ms 332 KB Output is correct
8 Correct 27 ms 332 KB Output is correct
9 Correct 51 ms 748 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 18 ms 588 KB Output is correct
12 Correct 140 ms 972 KB Output is correct
13 Correct 56 ms 1156 KB Output is correct
14 Correct 4 ms 460 KB Output is correct
15 Correct 15 ms 460 KB Output is correct
16 Runtime error 331 ms 35452 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -