Submission #113057

#	Time	Username	Problem	Language	Result	Execution time	Memory
113057		oolimry	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1239 ms	91304 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int n = N;
    int m = M;
    typedef pair<long long, long long> ii;
    const long long inf = 10234567890123456ll;

    ii value[n];
    fill(value, value + n, ii(inf,inf));

    for(int i = 0;i < K;i++){
        value[P[i]] = ii(0,0);
    }

    multiset<ii> s;
    for(int i = 0;i < N;i++){
        s.insert(ii(value[i].second, i));
    }

    vector<ii> adj[n];
    for(int i = 0;i < m;i++){
        int a = R[i][0];
        int b = R[i][1];
        adj[a].push_back(ii(b,L[i]));
        adj[b].push_back(ii(a,L[i]));
    }



    while(!s.empty()){
        int u = s.begin()->second;
        s.erase(s.begin());
        long long x = value[u].second;
        for(int i = 0;i < adj[u].size();i++){
            int v = adj[u][i].first;
            long long y = adj[u][i].second;
            if(x + y < value[v].second){
                //cout << u << " " << v << "\n";
                s.erase(s.find(ii(value[v].second, v)));
                if(x + y < value[v].first){
                    value[v].second = value[v].first;
                    value[v].first = x + y;
                }
                else{
                    value[v].second = x + y;
                }
                s.insert(ii(value[v].second, v));
            }

        }
    }


    return value[0].second;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:36:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < adj[u].size();i++){
                       ~~^~~~~~~~~~~~~~~

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