oj.uz

Submission #706966

# Submission time Handle Problem Language Result Execution time Memory
706966 2023-03-08T08:04:59 Z Nhoksocqt1 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 551 ms 50000 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, 0});
    }

    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] < 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 2644 KB Output is correct
2 Correct 2 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 2676 KB Output is correct
6 Correct 2 ms 2760 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 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 2676 KB Output is correct
6 Correct 2 ms 2760 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2644 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 3196 KB Output is correct
14 Correct 2 ms 2676 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 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 2676 KB Output is correct
6 Correct 2 ms 2760 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2644 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 3196 KB Output is correct
14 Correct 2 ms 2676 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 417 ms 44744 KB Output is correct
17 Correct 74 ms 12656 KB Output is correct
18 Correct 83 ms 13904 KB Output is correct
19 Correct 551 ms 50000 KB Output is correct
20 Correct 258 ms 39528 KB Output is correct
21 Correct 32 ms 7872 KB Output is correct
22 Incorrect 344 ms 35204 KB Output isn't correct
23 Halted 0 ms 0 KB -