Submission #848389

#	Time	Username	Problem	Language	Result	Execution time	Memory
848389		Warinchai	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	415 ms	91924 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> >v[100005];
pair<long long,long long> dis[100005];
bool vis[100005];
priority_queue<pair<long long,int>,vector<pair<long long,int> >, greater<pair<long long,int> > >pq;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for(int i=0;i<m;i++){
        int st=r[i][0];
        int en=r[i][1];
        int w=l[i];
        v[st].push_back({en,w});
        v[en].push_back({st,w});
    }
    for(int i=0;i<n;i++){
        dis[i].first=dis[i].second=LLONG_MAX;
    }
    for(int i=0;i<k;i++){
        dis[p[i]].first=dis[p[i]].second=0;
        pq.push({0,p[i]});
    }
    while(!pq.empty()){
        int x=pq.top().second;
        long long cost=pq.top().first;
        pq.pop();
        if(vis[x]){
            continue;
        }
        vis[x]=1;
        for(int i=0;i<v[x].size();i++){
            int nn=v[x][i].first;
            long long nc=cost+v[x][i].second;
            if(nc<dis[nn].second){
                dis[nn].second=nc;
                if(dis[nn].second<dis[nn].first)swap(dis[nn].second,dis[nn].first);
                if(dis[nn].second!=LLONG_MAX){
                    pq.push({dis[nn].second,nn});
                }
            }
        }
    }
    return dis[0].second;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int i=0;i<v[x].size();i++){
      |                     ~^~~~~~~~~~~~

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