Submission #727380

#	Time	Username	Problem	Language	Result	Execution time	Memory
727380		MisterReaper	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	525 ms	49632 KiB

crocodile

// author: MisterReaper (Ahmet Alp Orakci)
#include <bits/stdc++.h>
using namespace std;
#define Data pair <Best, int> 
#define ONLINE_JUDGE

const int MAXN = 1e5 + 5;
const long long INF = 1e18;

#ifndef ONLINE_JUDGE
    #include "debug.h"
    #define OPEN freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    #define TIME cerr << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds ";
#else
    #define debug(...) void(23)
    #define OPEN void(0000)
    #define TIME void(232323233)
#endif

struct Best
{
    long long val1, val2;
    Best(long long a = INF, long long b = INF) : val1(a), val2(b) {}

    void add(long long x)
    {
        if(x <= val1)
        {
            val2 = val1;
            val1 = x;
        }

        else if(x <= val2)
        {
            val2 = x;
        }
    }
    bool ok() {return val1 != INF && val2 != INF;}
};

bool operator> (Best a, Best b)
{
    return (a.val2 != b.val2) ? a.val2 > b.val2 : a.val1 > b.val1;
}
bool operator< (Best a, Best b)
{
    return (a.val2 != b.val2) ? a.val2 < b.val2 : a.val1 < b.val1;
}
bool operator== (Best a, Best b)
{
    return a.val1 == b.val1 && a.val2 == b.val2;
}
bool operator!= (Best a, Best b)
{
    return !(a == b);
}

vector <pair <int, int>> graph[MAXN];
Best dists[MAXN];

int solve(int n, int m, int (*edges)[2], int* l, int k, int *entry)
{
    for(int i = 1; i <= m; i++)
    {
        int u = edges[i -1][0], v = edges[i -1][1], c = l[i -1];

        graph[u].emplace_back(v, c);
        graph[v].emplace_back(u, c);
    }

    priority_queue <Data, vector <Data>, greater <Data>> pq;

    for(int i = 1; i <= k; i++)
    {
        int x = entry[i -1]; 
        dists[x] = {0, 0};
        pq.emplace(dists[x], x);
    }

    while(!pq.empty())
    {
        Best val = pq.top().first; int node = pq.top().second;
        pq.pop();
        
        if(dists[node] != val) continue;
        debug(node);

        for(auto [child, c] : graph[node])
        {
            int cost = val.val2 + c;
            Best childval = dists[child]; childval.add(cost);
            debug(childval.val1, childval.val2);

            if(childval < dists[child])
            {
                dists[child] = childval;
                if(dists[child].ok())
                {
                    pq.emplace(childval, child);
                }
            }
        }
    }

    if(dists[0].val2 == INF) 
    {
        cout << "BAD";
        return -1;
    }

    return dists[0].val2; 
}

int travel_plan(int n, int m, int (*r)[2], int* l, int k, int *p)
{
    return solve(n, m, r, l, k, p);
}

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