Submission #772772

#	Time	Username	Problem	Language	Result	Execution time	Memory
772772		canadavid1	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	611 ms	91672 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using u64 = uint64_t;

struct Node
{
    vector<Node*> n;
    vector<int> ew;
    i32 tte=INT_MAX;
    i32 min_val_neigh=INT_MAX;
};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    vector<Node> node(N);
    for(int i = 0; i < M; i++)
    {
        node[R[i][0]].n.push_back(&node[R[i][1]]);
        node[R[i][0]].ew.push_back(L[i]);
        node[R[i][1]].n.push_back(&node[R[i][0]]);
        node[R[i][1]].ew.push_back(L[i]);
    }
    priority_queue<pair<i32,Node*>,vector<pair<i32,Node*>>,greater<pair<i32,Node*>>> q;
    for(int i = 0; i < K; i++) q.push({0,&node[P[i]]});
    while(q.size())
    {
        auto[p,a] = q.top(); q.pop();
        //cout << a-&node[0] << " " << p << "\n";
        if(a->tte!=INT_MAX) continue;
        a->tte = p;
        //if(a==&node[0]) return a->tte;
        for(int i = 0; i < a->n.size();i++)
        {
            auto b = a->n[i];
            auto w = a->ew[i];
            if(b->tte != INT_MAX) continue;
            if(b->min_val_neigh==INT_MAX) b->min_val_neigh = w+a->tte;
            else
            {
                int ptime;
                if(b->min_val_neigh > a->tte+w)
                {
                    ptime = b->min_val_neigh;
                    b->min_val_neigh = a->tte+w;
                }
                else ptime = a->tte+w;
                
                q.push({ptime,b});
            }
        }
    }
    return node[0].tte;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:29:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto[p,a] = q.top(); q.pop();
      |             ^
crocodile.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i = 0; i < a->n.size();i++)
      |                        ~~^~~~~~~~~~~~~

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