oj.uz

Submission #308861

# Submission time Handle Problem Language Result Execution time Memory
308861 2020-10-02T05:31:56 Z talant117408 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 4 ms 4352 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);
        
        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
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 Incorrect 4 ms 4352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 4 ms 4352 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 Incorrect 4 ms 4352 KB Output isn't correct
4 Halted 0 ms 0 KB -