oj.uz

Submission #608837

# Submission time Handle Problem Language Result Execution time Memory
608837 2022-07-27T10:40:25 Z MohamedFaresNebili Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 20576 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>;
            using pi = pair<int, pair<int, 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], DP[100][100];
            bool pr[100];
            void precomputation(int i) {
                priority_queue<pi, vector<pi>, greater<pi>> pq;
                pq.push({0, {0, i}}); vector<vector<int>> D;
                D = vector<vector<int>> (R, vector<int>(C, oo));
                vector<vector<bool>> vis(R, vector<bool>(C, 0));
                D[0][i] = 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] || vis[U][V]) continue;
                    vis[U][V] = 1;
                    if(V < C - 1) {
                        if(!vis[U][V + 1] && 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(!vis[U][V - 1] && 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(!vis[U + 1][V] && 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}});
                        }
                    }
                }
                for(int l = 0; l < C; l++)
                    DP[i][l] = D[R - 1][l];
                pr[i] = 1;
            }
            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];
            }
 
            void changeH(int P, int Q, int W) {
                H[P][Q] = W;
                for(int l = 0; l < C; l++) pr[l] = 0;
            }
            void changeV(int P, int Q, int W) {
                K[P][Q] = W;
                for(int l = 0; l < C; l++) pr[l] = 0;
            }
 
            int escape(int V1, int V2) {
                if(!pr[V1]) precomputation(V1);
                return DP[V1][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 247 ms 12688 KB Output is correct
2 Correct 271 ms 12724 KB Output is correct
3 Correct 337 ms 14320 KB Output is correct
4 Correct 250 ms 12692 KB Output is correct
5 Correct 275 ms 12792 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 69 ms 1352 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 784 KB Output is correct
2 Correct 226 ms 928 KB Output is correct
3 Correct 136 ms 772 KB Output is correct
4 Correct 138 ms 844 KB Output is correct
5 Correct 136 ms 776 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 100 ms 772 KB Output is correct
10 Correct 1 ms 308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 16736 KB Output is correct
2 Correct 1519 ms 16612 KB Output is correct
3 Correct 874 ms 16604 KB Output is correct
4 Correct 906 ms 17472 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 724 KB Output is correct
2 Correct 216 ms 972 KB Output is correct
3 Correct 137 ms 776 KB Output is correct
4 Correct 141 ms 772 KB Output is correct
5 Correct 143 ms 724 KB Output is correct
6 Correct 879 ms 16608 KB Output is correct
7 Correct 1511 ms 16612 KB Output is correct
8 Correct 853 ms 16620 KB Output is correct
9 Correct 907 ms 17468 KB Output is correct
10 Correct 256 ms 12676 KB Output is correct
11 Correct 277 ms 12720 KB Output is correct
12 Correct 308 ms 14324 KB Output is correct
13 Correct 261 ms 12684 KB Output is correct
14 Correct 250 ms 12688 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 312 KB Output is correct
23 Correct 2 ms 312 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 64 ms 1340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 99 ms 772 KB Output is correct
28 Execution timed out 20016 ms 18708 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 768 KB Output is correct
2 Correct 211 ms 920 KB Output is correct
3 Correct 135 ms 772 KB Output is correct
4 Correct 136 ms 772 KB Output is correct
5 Correct 133 ms 724 KB Output is correct
6 Correct 869 ms 16612 KB Output is correct
7 Correct 1503 ms 16596 KB Output is correct
8 Correct 852 ms 16608 KB Output is correct
9 Correct 904 ms 17460 KB Output is correct
10 Correct 259 ms 12796 KB Output is correct
11 Correct 271 ms 12688 KB Output is correct
12 Correct 319 ms 14272 KB Output is correct
13 Correct 269 ms 12684 KB Output is correct
14 Correct 253 ms 12688 KB Output is correct
15 Incorrect 831 ms 20576 KB Output isn't correct
16 Halted 0 ms 0 KB -