oj.uz

Submission #249738

# Submission time Handle Problem Language Result Execution time Memory
249738 2020-07-15T16:25:00 Z eohomegrownapps Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 1 ms 512 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> adjlist; //val,node
ll n,k;
vector<ll> exits; //k of them
ll INF = 1e18;
ll dijkstra(){
    //source is 0
    vector<pair<ll,ll>> distances(n,{INF,INF}); //second then first
    priority_queue<pair<pair<ll,ll>,ll>,vector<pair<pair<ll,ll>,ll>>,greater<pair<pair<ll,ll>,ll>>> pq;
    //second,first
    for (ll i = 0; i<k; i++){
        distances[exits[i]]={0,0};
        pq.push({{0,0},exits[i]});
    }
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        /*cout<<"======\n";
        cout<<f.second<<'\n';
        for (auto p : distances){
            cout<<p.first<<" "<<p.second<<'\n';
        }*/
        //cout<<"check: "<<distances[f.second].first<<" "<<distances[f.second].second<<", "<<f.first.first<<" "<<f.first.second<<'\n';
        if (distances[f.second]<f.first){
            continue; //can't remember this condition
        }
        for (auto p : adjlist[f.second]){
            ll dist = p.first;
            ll node = p.second;
            ll newval = distances[f.second].first+dist;
            //cout<<newval<<'\n';
            if (newval<=distances[node].second){
                distances[node].first=distances[node].second;
                distances[node].second=newval;
                pq.push({distances[node],node});
            } else if (newval<=distances[node].first){
                distances[node].first=newval;
                pq.push({distances[node],node});
            }
        }
    }
    return distances[0].first;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n=N;k=K;
    adjlist.resize(n);
    for (ll i = 0; i<M; i++){
        adjlist[R[i][0]].push_back({L[i],R[i][1]});
        adjlist[R[i][1]].push_back({L[i],R[i][0]});
    }
    exits = vector<ll>(P,P+k);
    return dijkstra();
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Incorrect 1 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Incorrect 1 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Incorrect 1 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -