Submission #255605

#	Time	Username	Problem	Language	Result	Execution time	Memory
255605		SamAnd	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	715 ms	57176 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 100005;
const int INF = 1000000009;

struct ban
{
    int x;
    int d;
    ban(){}
    ban(int x, int d)
    {
        this->x = x;
        this->d = d;
    }
};

int n;
vector<ban> g[N];

bool c[N];

int min1[N], min2[N];

bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N;

    for (int i = 0; i < M; ++i)
    {
        int x = R[i][0];
        int y = R[i][1];
        int z = L[i];
        g[x].push_back(ban(y, z));
        g[y].push_back(ban(x, z));
    }

    for (int x = 0; x < n; ++x)
    {
        min1[x] = min2[x] = INF;
    }

    priority_queue<ban> q;
    for (int i = 0; i < K; ++i)
    {
        int x = P[i];

        min1[x] = min2[x] = 0;
        q.push(ban(x, 0));
    }

    while (!q.empty())
    {
        ban t;
        do
        {
            t = q.top();
            q.pop();
        } while (c[t.x]);
        c[t.x] = true;
        if (t.x == 0)
            return t.d;

        for (int i = 0; i < g[t.x].size(); ++i)
        {
            ban h = g[t.x][i];
            h.d += t.d;
            if (h.d <= min1[h.x])
            {
                min2[h.x] = min1[h.x];
                min1[h.x] = h.d;
            }
            else if (h.d <= min2[h.x])
            {
                min2[h.x] = h.d;
            }
            q.push(ban(h.x, min2[h.x]));
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:75:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[t.x].size(); ++i)
                         ~~^~~~~~~~~~~~~~~
crocodile.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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