oj.uz

Submission #308862

# Submission time Handle Problem Language Result Execution time Memory
308862 2020-10-02T05:32:55 Z talant117408 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 756 ms 72912 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 1e5+7;
const ll INF = 9e18;
vector <pii> dis(N, {INF, INF});
vector <vector <pii>> graph(N);
vector <int> pp;

void dijkstra(){
    
    priority_queue <pii> K;
    for(auto to : pp){
        K.push(mp(0, to));
        dis[to] = {0, 0};
    }
    
    while(K.size()){
        auto v = K.top(); K.pop();
        v.first = abs(v.first);
        if(v.first > dis[v.second].second) continue;
        for(auto to : graph[v.second]){
            if(v.first+to.second < dis[to.first].second){
                dis[to.first].second = v.first+to.second;
                if(dis[to.first].first > dis[to.first].second) 
                    swap(dis[to.first].first, dis[to.first].second);
                if(dis[to.first].second != INF)
                    K.push(mp(-dis[to.first].second, to.first));
            }
        }
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    for(int i = 0; i < m; i++){
        graph[r[i][0]].pb(mp(r[i][1], (ll)l[i]));
        graph[r[i][1]].pb(mp(r[i][0], (ll)l[i]));
    }
    
    for(int i = 0; i < k; i++)
        pp.pb(p[i]);
    dijkstra();
    
    return dis[0].second;
}

/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

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
14
*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 4 ms 4352 KB Output is correct
7 Correct 4 ms 4352 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 5 ms 4608 KB Output is correct
10 Correct 3 ms 4224 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 7 ms 4864 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 3 ms 4224 KB Output is correct
15 Correct 4 ms 4352 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 4 ms 4352 KB Output is correct
7 Correct 4 ms 4352 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 5 ms 4608 KB Output is correct
10 Correct 3 ms 4224 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 7 ms 4864 KB Output is correct
13 Correct 6 ms 4992 KB Output is correct
14 Correct 3 ms 4224 KB Output is correct
15 Correct 4 ms 4352 KB Output is correct
16 Correct 605 ms 67564 KB Output is correct
17 Correct 109 ms 14456 KB Output is correct
18 Correct 126 ms 16632 KB Output is correct
19 Correct 756 ms 72912 KB Output is correct
20 Correct 344 ms 56056 KB Output is correct
21 Correct 47 ms 9592 KB Output is correct
22 Incorrect 380 ms 51192 KB Output isn't correct