Submission #308863

#	Time	Username	Problem	Language	Result	Execution time	Memory
308863		talant117408	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1054 ms	75512 KiB

crocodile

#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(){
    
    set <pii> K;
    for(auto to : pp){
        K.insert(mp(0, to));
        dis[to] = {0, 0};
    }
    
    while(K.size()){
        auto it = K.begin(); K.erase(K.begin());
        pii v = *it;
        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.insert(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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11