oj.uz

Submission #308849

# Submission time Handle Problem Language Result Execution time Memory
308849 2020-10-02T05:01:00 Z talant117408 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 4 ms 4224 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);

void dijkstra(int p){
    dis[p].second = dis[p].first;
    dis[p].first = 0;
    
    priority_queue <pii> K;
    K.push(mp(0, p));
    
    while(K.size()){
        auto v = K.top(); K.pop();
        v.first *= -1;
        
        for(auto to : graph[v.second]){
            if(dis[to.first].first == dis[to.first].second && dis[to.first].first == v.first+to.second) continue;
            if(v.first+to.second <= dis[to.first].second){
                if(v.first+to.second <= dis[to.first].first){
                    dis[to.first].second = dis[to.first].first;
                    dis[to.first].first = v.first+to.second;
                }
                else{
                    dis[to.first].second = v.first+to.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[]){
    int i;
    for(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(i = 0; i < k; i++){
        dijkstra(p[i]);
    }
    
    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 4224 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 4224 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 4224 KB Output isn't correct
4 Halted 0 ms 0 KB -