Submission #707066

#	Time	Username	Problem	Language	Result	Execution time	Memory
707066		Nhoksocqt1	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	467 ms	62844 KiB

crocodile

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

vector<ii> adj[MAXN];
ll dist[MAXN][2];
int numNode, numEdge, numExit;

struct State {
    ll dis;
    int u, typ;

    bool operator < (const State &s) const {
        return dis > s.dis;
    }
};

int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
    numNode = _N, numEdge = _M, numExit = _K;
    for (int i = 0; i < numEdge; ++i) {
        int u(_R[i][0]), v(_R[i][1]), w(_L[i]);
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    for (int i = 0; i < numNode; ++i)
        dist[i][0] = dist[i][1] = 1e18;

    priority_queue<State> heap;
    for (int i = 0; i < numExit; ++i) {
        int u(_P[i]);
        dist[u][0] = dist[u][1] = 0;
        heap.push({0, u, 1});
    }

    while(heap.size()) {
        ll dis(heap.top().dis);
        int u(heap.top().u), type(heap.top().typ);
        heap.pop();

        if(dis != dist[u][type])
            continue;

        for (int it = 0; it < int(adj[u].size()); ++it) {
            int v(adj[u][it].fi), w(adj[u][it].se);
            if(dist[v][0] > dis + w) {
                if(dist[v][0] != dist[v][1] && dist[v][0] < 1e18) {
                    dist[v][1] = dist[v][0];
                    heap.push({dist[v][1], v, 1});
                }

                dist[v][0] = dis + w;
            } else
                if(dist[v][1] > dis + w) {
                    dist[v][1] = dis + w;
                    heap.push({dis + w, v, 1});
                }
        }
    }

    return dist[0][1];
}

Compilation message (stderr)

crocodile.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
crocodile.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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