Submission #644266

#	Time	Username	Problem	Language	Result	Execution time	Memory
644266		ToroTN	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	583 ms	64728 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
int n,m,k,p[100005],y,cost,d[100005][2],u,vis[100005],deg[100005];
vector<pair<int,int> > g[100005];
priority_queue<pair<int,int> > pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N;
    for(int i=1;i<=n;i++)
    {
        d[i][0]=1e9;
        d[i][1]=1e9;
    }
    m=M;
    for(int i=0;i<m;i++)
    {
        g[R[i][0]+1].pb({R[i][1]+1,L[i]});
        g[R[i][1]+1].pb({R[i][0]+1,L[i]});
    }
    k=K;
    for(int i=0;i<k;i++)
    {
        p[i+1]=P[i]+1;
    }
    for(int i=1;i<=k;i++)
    {
        d[p[i]][0]=0;
        d[p[i]][1]=0;
        pq.push({0,p[i]});
    }
    /*while(!pq.empty())
    {
        printf("%d %d\n",pq.top().X,pq.top().Y);
        pq.pop();
    }*/
    while(!pq.empty())
    {
        u=pq.top().Y;
        //printf("%d %d %d\n",u,d[u][0],d[u][1]);
        pq.pop();
        if(vis[u]==1)continue;
        vis[u]=1;
        for(auto [y,cost]:g[u])
        {
            // if(d[y][0]==2e9&&d[y][1]==2e9)
            // {
            //     d[y][0]=d[u][1]+cost;
            //     d[y][1]=d[u][1]+cost;
            //     pq.push({-d[y][1],y});
            //     continue;
            // }
            if(d[u][1]+cost<=d[y][0])
            {
                d[y][1]=d[y][0];
                d[y][0]=d[u][1]+cost;
            }else if(d[u][1]+cost<d[y][1])
            {
                d[y][1]=d[u][1]+cost;
            }
             if(++deg[y]>=2&&vis[y]==0)
                {
                    pq.push({-d[y][1],y});
                }
        }
    }
    return d[1][1];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for(auto [y,cost]:g[u])
      |                  ^

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