Submission #255411

#	Time	Username	Problem	Language	Result	Execution time	Memory
255411		hhh07	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	680 ms	73068 KiB

crocodile

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include <cmath>
#include <climits>
#include <cstring>
#include "crocodile.h"
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;

vector<vector<ii>> adjList(100007, vector<ii>());
const int INF = 1e9 + 7;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    for (ll i = 0; i < m; i++){
        adjList[r[i][0]].push_back(make_pair(r[i][1], l[i]));
        adjList[r[i][1]].push_back(make_pair(r[i][0], l[i]));
    }
    
    vector<ii> t(n, {INF, INF});
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for (ll i = 0; i < k; i++){
        t[p[i]] = {0, 0};
        pq.push({0, p[i]});
    }
    
    while(!pq.empty()){
        auto curr = pq.top();
        pq.pop();
        if (t[curr.second].first != curr.first)
            continue;
        for (ll i = 0; i < adjList[curr.second].size(); i++){
            ll d = adjList[curr.second][i].second, idx = adjList[curr.second][i].first;
            ll val = curr.first + d;
            if (t[idx].first > val){
                int prev = t[idx].first;
                t[idx].first = val;
                if (t[idx].second > t[idx].first)
                    swap(t[idx].first, t[idx].second);
                
                if (t[idx].first != prev)
                    pq.push({t[idx].first, idx});
            }
            
            
        }
    }
    
    
    return t[0].first;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:38:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll i = 0; i < adjList[curr.second].size(); i++){
                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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