oj.uz

Submission #707066

# Submission time Handle Problem Language Result Execution time Memory
707066 2023-03-08T11:20:12 Z Nhoksocqt1 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 467 ms 62844 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 1 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 1 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2944 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 5 ms 3156 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 1 ms 2672 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 3 ms 2944 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 5 ms 3156 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 399 ms 57440 KB Output is correct
17 Correct 66 ms 14440 KB Output is correct
18 Correct 90 ms 15932 KB Output is correct
19 Correct 467 ms 62844 KB Output is correct
20 Correct 279 ms 47496 KB Output is correct
21 Correct 34 ms 7920 KB Output is correct
22 Correct 289 ms 44664 KB Output is correct