Submission #639736

#	Time	Username	Problem	Language	Result	Execution time	Memory
639736		finn__	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	545 ms	93340 KiB

crocodile

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

typedef pair<unsigned, uint64_t> edge;

struct node
{
    unsigned u;
    uint64_t w;

    bool operator<(node const &x) const
    {
        return w > x.w;
    }
};

int travel_plan(int n, int m, int edges[][2], int len[], int k, int p[])
{
    vector<vector<edge>> g(n);

    for (unsigned i = 0; i < m; i++)
    {
        unsigned u = edges[i][0], v = edges[i][1];
        uint64_t w = len[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }

    vector<uint64_t> d1(n, UINT64_MAX), d2(n, UINT64_MAX);
    priority_queue<node> q;
    vector<bool> finished(n, 0);

    for (unsigned i = 0; i < k; i++)
    {
        d1[p[i]] = 0;
        d2[p[i]] = 0;
        q.push((node){p[i], 0});
    }

    while (!q.empty())
    {
        unsigned u = q.top().u;
        uint64_t w = q.top().w;
        q.pop();

        if (!finished[u] && w == d2[u])
        {
            finished[u] = 1;

            if (w != UINT64_MAX)
            {
                for (auto const &[v, y] : g[u])
                {
                    if (!finished[v] && y != UINT64_MAX)
                    {
                        if (w + y < d1[v])
                        {
                            d2[v] = d1[v];
                            d1[v] = w + y;
                            q.push({v, d2[v]});
                        }
                        else if (w + y < d2[v])
                        {
                            d2[v] = w + y;
                            q.push({v, d2[v]});
                        }
                    }
                }
            }
        }
    }

    return d2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:22:28: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   22 |     for (unsigned i = 0; i < m; i++)
      |                          ~~^~~
crocodile.cpp:34:28: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   34 |     for (unsigned i = 0; i < k; i++)
      |                          ~~^~~
crocodile.cpp:38:26: warning: narrowing conversion of '*(p + ((sizetype)(((long unsigned int)i) * 4)))' from 'int' to 'unsigned int' [-Wnarrowing]
   38 |         q.push((node){p[i], 0});
      |                       ~~~^

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