Submission #900260

#	Time	Username	Problem	Language	Result	Execution time	Memory
900260		Sir_Ahmed_Imran	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	2024 ms	185672 KiB

crocodile

                              ///~~~LOTA~~~///
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 100000
#define MAXM 1000000
ll dp[MAXN];
ll dist[MAXN];
vector<pair<int,ll>> a[MAXN]; 
int travel_plan(int n,int m,int e[MAXM][2],int t[MAXM],int k,int P[MAXN]){
    ll q;
    int p;
    for(int i=0;i<n;i++)
        dist[i]=dp[i]=1e17;
    for(int i=0;i<m;i++){
        a[e[i][0]].append({e[i][1],t[i]});
        a[e[i][1]].append({e[i][0],t[i]});
    }
    multiset<pair<ll,int>> s;
    for(int i=0;i<k;i++){
        dist[P[i]]=0;
        s.insert({0,P[i]});
    }
    while(!s.empty()){
        p=(*s.begin()).ss;
        q=(*s.begin()).ff;
        s.erase(s.begin());
        if(q<dist[p])
            dist[p]=q;
        else if(q<dp[p]){
            dp[p]=q;
            for(auto& i:a[p])
                s.insert({q+i.ss,i.ff});
        }
    }
    if(dp[0]==1e17) dp[0]=-1;
    return dp[0];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 0 / 11