oj.uz

Submission #1023921

# Submission time Handle Problem Language Result Execution time Memory
1023921 2024-07-15T09:34:00 Z dozer Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define mid (l + r) / 2
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005


const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

static int H[5000][200];
static int V[5000][200];

int h[5000][200], v[5000][200], r, c;
int ans[200][5000][200];

void dijkstra(){
	for (int I = 0; I < c; I++){
		priority_queue<array<int, 3>> q;
		for(int i = 0; i < r; i++) for (int j = 0; j < c; j++) ans[I][i][j] = modulo;
		
		ans[I][r - 1][I] = 0;
		q.push({0, r - 1, I});
		

		while(!q.empty()){
			array<int, 3> tmp = q.top();
			q.pop();
			int d = -tmp[0], x = tmp[1], y = tmp[2];
			if (d > ans[I][x][y]) continue;
			if (y + 1 < c){
				if (ans[I][x][y + 1] > d + h[x][y]){
					ans[I][x][y + 1] = d + h[x][y];
					q.push({-ans[I][x][y + 1], x, y + 1});
				}
			}

			if (y > 0){
				if (ans[I][x][y - 1] > d + h[x][y - 1]){
					ans[I][x][y - 1] = d + h[x][y - 1];
					q.push({-ans[I][x][y - 1], x, y - 1});
				}
			}

			if (x > 0){
				if (ans[I][x - 1][y] > d + v[x - 1][y]){
					ans[I][x - 1][y] = d + v[x - 1][y];
					q.push({-ans[I][x - 1][y], x - 1, y});
				}
			}
		}
	}
		
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R, c = C;
    for (int i = 0; i < R; i++){
    	for (int j = 0; j < C; j++){
    		h[i][j] = H[i][j], v[i][j] = V[i][j];
    		//cout<<h[i][j]<<sp<<v[i][j]<<sp;
    	}
    	//cout<<endl;
    }

    dijkstra();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    dijkstra();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    dijkstra();
}

int escape(int V1, int V2) {
    return ans[V2][0][V1];
}

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;
      |      ^~~
wombats.cpp:29:12: warning: 'V' defined but not used [-Wunused-variable]
   29 | static int V[5000][200];
      |            ^
wombats.cpp:28:12: warning: 'H' defined but not used [-Wunused-variable]
   28 | static int H[5000][200];
      |            ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15960 KB Output is correct
2 Correct 44 ms 15964 KB Output is correct
3 Correct 80 ms 18768 KB Output is correct
4 Correct 44 ms 15960 KB Output is correct
5 Correct 45 ms 15964 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 42 ms 3320 KB Output is correct
12 Correct 1 ms 856 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9983 ms 9356 KB Output is correct
2 Correct 17349 ms 9608 KB Output is correct
3 Correct 10049 ms 9436 KB Output is correct
4 Correct 10061 ms 9436 KB Output is correct
5 Correct 9470 ms 9556 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 444 KB Output is correct
9 Execution timed out 20029 ms 9260 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 24144 KB Output is correct
2 Correct 825 ms 23980 KB Output is correct
3 Correct 296 ms 23896 KB Output is correct
4 Correct 316 ms 25172 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9553 ms 9360 KB Output is correct
2 Correct 18010 ms 9416 KB Output is correct
3 Correct 10304 ms 9436 KB Output is correct
4 Correct 9708 ms 9440 KB Output is correct
5 Correct 9281 ms 9300 KB Output is correct
6 Correct 290 ms 23900 KB Output is correct
7 Correct 844 ms 23972 KB Output is correct
8 Correct 308 ms 23900 KB Output is correct
9 Correct 335 ms 25200 KB Output is correct
10 Correct 44 ms 16108 KB Output is correct
11 Correct 44 ms 15964 KB Output is correct
12 Correct 101 ms 18764 KB Output is correct
13 Correct 45 ms 15960 KB Output is correct
14 Correct 53 ms 15964 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 2 ms 1112 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 1 ms 956 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 760 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 69 ms 3156 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Execution timed out 20082 ms 9348 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9485 ms 9300 KB Output is correct
2 Correct 17053 ms 9540 KB Output is correct
3 Correct 10036 ms 9296 KB Output is correct
4 Correct 9917 ms 9436 KB Output is correct
5 Correct 9560 ms 9236 KB Output is correct
6 Correct 302 ms 23900 KB Output is correct
7 Correct 841 ms 23976 KB Output is correct
8 Correct 317 ms 24152 KB Output is correct
9 Correct 335 ms 25168 KB Output is correct
10 Correct 44 ms 15960 KB Output is correct
11 Correct 44 ms 15960 KB Output is correct
12 Correct 82 ms 18768 KB Output is correct
13 Correct 44 ms 15964 KB Output is correct
14 Correct 45 ms 15960 KB Output is correct
15 Runtime error 4248 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -