Submission #155375

#	Time	Username	Problem	Language	Result	Execution time	Memory
155375		arnold518	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1247 ms	76188 KiB

crocodile

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e15;

int N, M, K;
vector<pii> adj[MAXN+10];
ll dist[MAXN+10];
int vis[MAXN+10];

struct Queue
{
    int u; ll w;
    bool operator < (const Queue &p) const { return w>p.w; }
};

int travel_plan(int _N, int _M, int R[][2], int L[], int _K, int P[])
{
    int i, j;
    N=_N; M=_M; K=_K;

    for(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]});
    }

    priority_queue<Queue> PQ;
    for(i=0; i<K; i++) PQ.push({P[i], 0}), vis[P[i]]=1;

    while(!PQ.empty())
    {
        Queue T=PQ.top(); PQ.pop();
        if(vis[T.u]==2) continue;
        vis[T.u]++;
        if(vis[T.u]<2) continue;
        dist[T.u]=T.w;

        for(auto nxt : adj[T.u]) PQ.push({nxt.first, T.w+nxt.second});
    }
    return dist[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:25:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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