Submission #526009

#	Time	Username	Problem	Language	Result	Execution time	Memory
526009		MasterTaster	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	519 ms	93420 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<ll, ll>
#define xx first
#define yy second
#define INF 1000000000000010
#define MAXN 100010

using namespace std;

pii d[MAXN];
int n, m, k, p[MAXN];
bool bio[MAXN];
vector<pii> g[MAXN];

void upd(int u, ll x)
{
    if (x<d[u].xx) { d[u].yy=d[u].xx; d[u].xx=x; }
    else if (x<=d[u].yy) { d[u].yy=x; }
}

int dijkstra(int s)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i=0; i<n; i++) d[i].xx=d[i].yy=INF;
    for (int i=0; i<k; i++)
    {
        pq.push({0, p[i]});
        d[p[i]].xx=0; d[p[i]].yy=0;
    }

    while (!pq.empty())
    {
        int u=pq.top().yy; pq.pop();
        //cout<<"na vrhu mie "<<u<<" "<<d[u].xx<<" "<<d[u].yy<<endl;
        if (bio[u]) continue;
        bio[u]=true;
        for (auto edge:g[u])
        {
            int v=edge.xx; ll len=edge.yy;
            //upd(v, d[u]+len);
            if (d[u].yy+len<d[v].yy)
            {
                //cout<<"sace apdejt "<<v<<" "<<d[v].xx<<" "<<d[v].yy<<endl;
                upd(v, d[u].yy+len);
                //cout<<"posle laganog apdejta "<<v<<" "<<d[v].xx<<" "<<d[v].yy<<endl;
                pq.push({d[v].yy, v});
            }
        }
    }
    return d[0].yy;
}

int travel_plan(int nn, int mm, int r[][2], int ww[], int kk, int pp[])
{
    n=nn; m=mm; k=kk;
    for (int i=0; i<k; i++) p[i]=pp[i];
    ///dummy=n
    for (int i=0; i<m; i++)
    {
        int u, v, w; u=r[i][0]; v=r[i][1]; w=ww[i];
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    for (int i=0; i<k; i++)
    {
        g[n].pb({p[i], 0});
        g[p[i]].pb({n, 0});
        d[p[i]].xx=0; d[p[i]].yy=0;
    }



    ll ret=dijkstra(n);

    //for (int i=0; i<n; i++) cout<<d[i].xx<<" "<<d[i].yy<<endl;
    return ret;
}

/*
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