Submission #1186344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186344		simona1230	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	506 ms	87740 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

const long long maxn=2*1e5;
long long n,m;

struct edge
{
    long long x,d;
    edge(){}
    edge(long long _x,long long _d)
    {
        x=_x;
        d=_d;
    }

    bool operator<(const edge&e)const
    {
        return e.d<d;
    }
};

vector<edge> v[maxn];
priority_queue<edge> q;
long long c[maxn],d[maxn];

void dijkstra()
{
    for(long long i=0;i<n;i++)
        if(c[i]==0)d[i]=1e18;

    while(q.size())
    {
        edge t=q.top();
        q.pop();
        c[t.x]++;

        if(c[t.x]!=2)
            continue;
        d[t.x]=t.d;

        for(long long i=0;i<v[t.x].size();i++)
        {
            edge nb=v[t.x][i];
            if(t.d+nb.d<=d[nb.x])
                q.push({nb.x,nb.d+t.d});
        }
    }
}

void ae(long long i,long long j,long long x)
{
    v[i].push_back({j,x});
    v[j].push_back({i,x});
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N;
    m=M;
    for(long long i=0;i<m;i++)
        ae(R[i][0],R[i][1],L[i]);

    for(long long i=0;i<K;i++)
    {
        c[P[i]]=1;
        q.push({P[i],0});
    }

    dijkstra();

    return d[0];
}

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