Submission #1096133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096133		I_FloPPed21	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	305 ms	117608 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+1;
const long long inf=1e18;
struct nod
{
    int unde;
    long long cost;
};

struct coada
{
    int unde;
    long long cost;
};

struct compare
{
    bool operator()(coada &x,coada &y)
    {
        return x.cost>y.cost;
    }
};
vector<nod>adj[N];
long long best[N][2];
int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
    for(int i=0; i<m; i++)
    {
        adj[r[i][0]].push_back({r[i][1],l[i]});
        adj[r[i][1]].push_back({r[i][0],l[i]});
    }


    for(int i=0; i<n; i++)
    {
        best[i][0]=best[i][1]=inf;
    }
    priority_queue<coada,vector<coada>,compare>pq;
    for(int i=0; i<k; i++)
    {
        best[p[i]][0]=0;
        best[p[i]][1]=0;
        pq.push({p[i],0});
    }
    while(!pq.empty())
    {
        int nod=pq.top().unde;
        long long cost=pq.top().cost;
        pq.pop();
        if(cost!=best[nod][1])
            continue;
        for(auto u:adj[nod])
        {
            if(best[u.unde][0]>cost+u.cost)
            {

                if(best[u.unde][1]!=best[u.unde][0])
                {
                    best[u.unde][1]=best[u.unde][0];
                    if(best[u.unde][1]!=inf)
                        pq.push({u.unde,best[u.unde][1]});
                }
                best[u.unde][0]=cost+u.cost;

            }
            else if(best[u.unde][1]>cost+u.cost)
            {
                best[u.unde][1]=cost+u.cost;
                pq.push({u.unde,best[u.unde][1]});
            }
        }
    }
    return best[0][1];
}

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