oj.uz

Submission #608770

# Submission time Handle Problem Language Result Execution time Memory
608770 2022-07-27T09:59:35 Z MohamedFaresNebili Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 16588 KB 
#include <bits/stdc++.h>
#include "wombats.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
 
            using namespace std;
 
            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            const int oo = 1000 * 1000 * 1000 + 7;
 
            int R, C, H[5000][200], K[5000][200], ST[500005];
            void build(int v, int l, int r) {
                if(l == r) {
                    ST[v] = K[l][0];
                    return;
                }
                build(v * 2, l, (l + r) / 2);
                build(v * 2 + 1, (l + r) / 2 + 1, r);
                ST[v] = ST[v * 2] + ST[v * 2 + 1];
            }
            void update(int v, int l, int r, int p, int val) {
                if(l == r) {
                    ST[v] = val;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md)
                    update(v * 2, l, md, p, val);
                else update(v * 2 + 1, md + 1, r, p, val);
                ST[v] = ST[v * 2] + ST[v * 2 + 1];
            }
            int query(int v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return 0;
                if(l >= lo && r <= hi)
                    return ST[v];
                return query(v * 2, l, (l + r) / 2, lo, hi)
                    +  query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
            }
            void init(int r, int c, int h[5000][200], int v[5000][200]) {
                R = r, C = c;
                for(int l = 0; l < R; l++)
                    for(int i = 0; i < C; i++)
                        H[l][i] = h[l][i],
                        K[l][i] = v[l][i];
                if(C == 1) build(1, 0, R - 2);
            }
 
            void changeH(int P, int Q, int W) { H[P][Q] = W; }
            void changeV(int P, int Q, int W) {
                K[P][Q] = W;
                if(C == 1) update(1, 0, R - 2, P, W);
            }
 
            using pi = pair<int, pair<int, int>>;
 
            int escape(int V1, int V2) {
                if(C == 1)
                    return query(1, 0, R - 2, 0, R - 2);
                priority_queue<pi, vector<pi>, greater<pi>> pq;
                pq.push({0, {0, V1}}); vector<vector<int>> D;
                D = vector<vector<int>> (R, vector<int>(C, oo));
                D[0][V1] = 0;
                while(!pq.empty()) {
                    int U = pq.top().ss.ff, V = pq.top().ss.ss;
                    int W = pq.top().ff; pq.pop();
                    if(W != D[U][V]) continue;
                    if(V < C - 1) {
                        if(D[U][V + 1] > D[U][V] + H[U][V]) {
                            D[U][V + 1] = D[U][V] + H[U][V];
                            pq.push({D[U][V + 1], {U, V + 1}});
                        }
                    }
                    if(V > 0) {
                        if(D[U][V - 1] > D[U][V] + H[U][V - 1]) {
                            D[U][V - 1] = D[U][V] + H[U][V - 1];
                            pq.push({D[U][V - 1], {U, V - 1}});
                        }
                    }
                    if(U < R - 1) {
                        if(D[U + 1][V] > D[U][V] + K[U][V]) {
                            D[U + 1][V] = D[U][V] + K[U][V];
                            pq.push({D[U + 1][V], {U + 1, V}});
                        }
                    }
                }
                return D[R - 1][V2];
            }

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 7 ms 12052 KB Output is correct
3 Correct 83 ms 14176 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 26 ms 340 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 19 ms 412 KB Output is correct
8 Correct 13 ms 340 KB Output is correct
9 Correct 17 ms 340 KB Output is correct
10 Correct 14 ms 400 KB Output is correct
11 Correct 7264 ms 1512 KB Output is correct
12 Correct 21 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 684 KB Output is correct
2 Correct 211 ms 908 KB Output is correct
3 Correct 121 ms 692 KB Output is correct
4 Correct 133 ms 680 KB Output is correct
5 Correct 120 ms 696 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 202 ms 724 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 16216 KB Output is correct
2 Correct 1303 ms 16236 KB Output is correct
3 Correct 664 ms 16224 KB Output is correct
4 Execution timed out 20018 ms 16512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 596 KB Output is correct
2 Correct 202 ms 864 KB Output is correct
3 Correct 131 ms 684 KB Output is correct
4 Correct 128 ms 684 KB Output is correct
5 Correct 134 ms 684 KB Output is correct
6 Correct 662 ms 16212 KB Output is correct
7 Correct 1337 ms 16232 KB Output is correct
8 Correct 645 ms 16224 KB Output is correct
9 Execution timed out 20022 ms 16588 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 680 KB Output is correct
2 Correct 202 ms 1000 KB Output is correct
3 Correct 138 ms 684 KB Output is correct
4 Correct 125 ms 684 KB Output is correct
5 Correct 122 ms 684 KB Output is correct
6 Correct 611 ms 16332 KB Output is correct
7 Correct 1272 ms 16248 KB Output is correct
8 Correct 611 ms 16216 KB Output is correct
9 Execution timed out 20098 ms 16548 KB Time limit exceeded
10 Halted 0 ms 0 KB -