Submission #1039673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039673		_callmelucian	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	289 ms	61736 KiB

crocodile

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
vector<pii> adj[mn];
int vis[mn];

struct helper {
    int best, secBest;

    helper() : best(INT_MAX), secBest(INT_MAX) {}
    helper (int b, int sb) : best(b), secBest(sb) {}

    bool push (int cur) {
        if (cur < best) return secBest = best, best = cur, 1;
        else {
            if (cur >= secBest) return 0;
            return secBest = cur, 1;
        }
    }

    bool operator < (helper o) const {
        if (best == o.best) return secBest > o.secBest;
        return best > o.best;
    }
} dist[mn];

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < m; i++) {
        adj[r[i][0]].push_back({r[i][1], l[i]});
        adj[r[i][1]].push_back({r[i][0], l[i]});
    }

    priority_queue<pii> pq;
    for (int i = 0; i < k; i++) {
        int u = p[i];
        vis[u] = 1, dist[u] = helper(0, 0);
        pq.push({0, u});
    }

    //for (int i = 1; i <= n; i++) pq.push({dist[i], i});

    while (pq.size()) {
        int u = pq.top().second; pq.pop();
        if (vis[u] == 2) continue;
        if (++vis[u] == 1) continue;

        for (auto [v, w] : adj[u])
            if (dist[v].push(dist[u].secBest + w)) pq.push({-dist[u].secBest - w, v});
    }
    return dist[0].secBest;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:57:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto [v, w] : adj[u])
      |                   ^

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