Submission #900262

#	Time	Username	Problem	Language	Result	Execution time	Memory
900262		Sir_Ahmed_Imran	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1109 ms	100936 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
int dp[MAXN];
int dist[MAXN];
multiset<pair<int,int>> s;
vector<pair<int,int>> a[MAXN]; 
int travel_plan(int n,int m,int e[MAXM][2],int t[MAXM],int k,int P[MAXN]){
    int p,q;
    for(int i=0;i<n;i++)
        dist[i]=dp[i]=1e9+7;
    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]});
    }
    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])
                if(q+i.ss<dp[i.ff])
                    s.insert({q+i.ss,i.ff});
        }
    }
    return dp[0];
}

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