Submission #17010

#	Time	Username	Problem	Language	Result	Execution time	Memory
17010		erdemkiraz	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	660 ms	153068 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e5 + 5;

int n, m;
int a[N], mn[N], mn2[N];
vector < ii > v[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N;
    m = M;
    for(int i = 0; i < m; i++) {
        int x = R[i][0] + 1;
        int y = R[i][1] + 1;
        int c = L[i];
        v[x].push_back(ii(y, c));
        v[y].push_back(ii(x, c));
    }
    priority_queue < ii > Q;
    memset(mn, 63, sizeof(mn));
    memset(mn2, 63, sizeof(mn2));
    for(int i = 0; i < K; i++) {
        int x = P[i] + 1;
        a[x] = 1;
        Q.push(ii(0, x));
        mn[x] = mn2[x] = 0;
    }
    while(!Q.empty()) {
        int c = -Q.top().first;
        int x = Q.top().second;
        Q.pop();
        if(c > mn2[x])
            continue;
        foreach(it, v[x]) {
            int u = it -> first;
            int e = it -> second;
            int cur = mn2[u];
            if(c + e < mn[u]) {
                mn2[u] = mn[u];
                mn[u] = c + e;
            }
            else
                mn2[u] = min(mn2[u], c + e);
            if(cur != mn2[u]) {
                Q.push(ii(-mn2[u], u));
            }
        }
    }
    return mn2[1];
}

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