Submission #497261

#	Time	Username	Problem	Language	Result	Execution time	Memory
497261		Skywk	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	669 ms	84580 KiB

crocodile

#include "crocodile.h"
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<math.h>
#include<queue>
#include<stack>
#define lmt 100000
#define LMT 1000000
#define mod 1000000007
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
 
using namespace std;

vector<pil> graph[lmt];
long long best[LMT];
bool once[LMT];

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for(int i=0; i<m;  i++)
    {
        int a=R[i][0], b=R[i][1];
        graph[a].push_back({b, L[i]});
        graph[b].push_back({a, L[i]});
    }
    
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for(int i=0, x; i<k; i++)
        pq.push({0, P[i]});

    for(int i=0; i<n; i++)
        best[i]=-1;
    while(!pq.empty())
    {
        auto p=pq.top();
        pq.pop();
        int x=p.second; long long w=p.first;

        if(best[x] != -1)
            continue;
        if(w!=0 && !once[x])
        {
            once[x]=true;
            continue;
        }

        best[x]=w;
        for(auto y : graph[x])
        {
            if(best[y.first] != -1)
                continue;
            pq.push({w+y.second, y.first});
        }
    }
    return best[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:37:18: warning: unused variable 'x' [-Wunused-variable]
   37 |     for(int i=0, x; i<k; i++)
      |                  ^

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