Submission #727376

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

crocodile

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};


// -------------------------------------------------- Main Code --------------------------------------------------

int sol(int n, int m, int (*edges)[2], int* l, int k, int *entry) {
    vector<array<int, 2>> g[n];
    for (int i = 0; i < m; i++) {
        int a = edges[i][0], b = edges[i][1], c = l[i];
        g[a].pb({b, c});
        g[b].pb({a, c});
    }

    priority_queue<pii, vector<pii>, greater<pii>> q;
    vii dis(n);
    vi vis(n, 0);
    for (int i = 0; i < k; i++) {
        int temp = entry[i];
        q.push({0, temp});
        dis[temp].pb(0); dis[temp].pb(0);
        vis[temp]++;
    }

    while (!q.empty()) {
        int src = q.top().s, dist = q.top().f; q.pop();
        if (vis[src] >= 2) continue;
        vis[src]++;
        if (vis[src] != 2) continue;
        if (src == 0) {
            return dist;
        }

        for (auto child : g[src]) {
            int ch = child[0], wt = child[1];
            if (dis[ch].size() == 2) {
                sort (all(dis[ch]));
                if (dist+wt < dis[ch][1]) {
                    dis[ch].pop_back();
                    dis[ch].pb(dist+wt);
                    q.push({dist+wt, ch});
                }
            }
            else {
                dis[ch].pb(dist+wt);
                q.push({dist+wt, ch});
            }
        }
    }
    // not needed
    cout << "BAD" << endl;
    return -1;
}

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

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