Submission #417693

#	Time	Username	Problem	Language	Result	Execution time	Memory
417693		iulia13	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	784 ms	93828 KiB

crocodile

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

#define ll long long

const int N = 1e5 + 5;
const int INF = 2e9;

struct ura{
    ll x, c;
    bool operator <(const ura &other) const{
        return c > other.c;
    }
};
vector <ura> g[N];
ll d[N];
int bagat[N];
priority_queue <ura> pq;
int cost[N][2];
int q[N];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    int i, j, inc = 1, sf = 0;
    for (i = 0; i < m ; i++)
        for (j = 0; j < 2; j++)
            g[r[i][j]].push_back({r[i][1 - j], l[i]});
    for (i = 0; i < n; i++)
        cost[i][0] = cost[i][1] = d[i] = INF;
    for (i = 0; i < k; i++)
    {
        d[p[i]] = 0;
        q[++sf] = p[i];
        cost[p[i]][0] = 0;
        cost[p[i]][1] = 0;
        bagat[p[i]] = 1;
    }
    while (inc <= sf)
    {
        int x = q[inc++];
        int c = d[x];
        for (auto u : g[x])
        {
            if (bagat[u.x])
                continue;
            int costnow = u.c + c;
            if (cost[u.x][1] < costnow)
                continue;
            if (costnow < cost[u.x][0])
            {
                cost[u.x][1] = cost[u.x][0];
                cost[u.x][0] = costnow;
            }
            else
            if (costnow < cost[u.x][1])
                cost[u.x][1] = costnow;
            pq.push({u.x, cost[u.x][1]});
        }
        if (inc > sf)
        {
            int ok = 1;
            while (ok && !pq.empty())
            {
                int x = pq.top().x;
                pq.pop();
                if (bagat[x])
                    continue;
                ok = 0;
                bagat[x] = 1;
                q[++sf] = x;
                d[x] = cost[x][1];
            }
        }
    }
    return d[0];
}

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