oj.uz

Submission #351221

# Submission time Handle Problem Language Result Execution time Memory
351221 2021-01-19T16:38:17 Z Mefarnis Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 262148 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#define maxm 200
#define maxn 5000
using namespace std;

int n,m;
int*** cost;
int edgeH[maxn][maxm];
int edgeV[maxn][maxm];

struct path {
	int r,c,dist;
	path(int _r , int _c , int _dist) {
		r = _r;
		c = _c;
		dist = _dist;
	}
};

bool operator<(const path& a , const path& b) {
	return a.dist > b.dist;
}

void dijkstra(int col) {
	for( int i = 0 ; i < n ; i++ )
		for( int j = 0 ; j < m ; j++ )
			cost[col][i][j] = -1;
	priority_queue<path> heap;
	heap.push(path(0,col,0));
	while(!heap.empty()) {
		path p = heap.top();
		heap.pop();
		int r = p.r;
		int c = p.c;
		if(cost[col][r][c] != -1)
			continue;
		int dist = p.dist;
		cost[col][r][c] = dist;
		if(c >= 1 && cost[col][r][c-1] == -1)
			heap.push(path(r,c-1,dist+edgeH[r][c-1]));
		if(c < m-1 && cost[col][r][c+1] == -1)
			heap.push(path(r,c+1,dist+edgeH[r][c]));
		if(r < n-1 && cost[col][r+1][c] == -1)
			heap.push(path(r+1,c,dist+edgeV[r][c]));
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R;
	m = C;
	for( int i = 0 ; i < n ; i++ )
		for( int j = 0 ; j < m-1 ; j++ )
			edgeH[i][j] = H[i][j];
	for( int i = 0 ; i < n-1 ; i++ )
		for( int j = 0 ; j < m ; j++ )
			edgeV[i][j] = V[i][j];
	cost = new int**[m];
	for( int col = 0 ; col < m ; col++ ) {
		cost[col] = new int*[n];
		for( int i = 0 ; i < n ; i++ )
			cost[col][i] = new int[m];
	}
	for( int i = 0 ; i < m ; i++ )
		dijkstra(i);
}

void changeH(int P, int Q, int W) {
	edgeH[P][Q] = W;
	for( int i = 0 ; i < m ; i++ )
		dijkstra(i);
}

void changeV(int P, int Q, int W) {
	edgeV[P][Q] = W;
	for( int i = 0 ; i < m ; i++ )
		dijkstra(i);
}

int escape(int V1, int V2) {
	return cost[V1][n-1][V2];
}

/*
int main() {
	
}
*/

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 86 ms 8300 KB Output is correct
2 Correct 84 ms 8428 KB Output is correct
3 Correct 163 ms 9964 KB Output is correct
4 Correct 85 ms 8300 KB Output is correct
5 Correct 84 ms 8300 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 81 ms 2796 KB Output is correct
12 Correct 2 ms 492 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16483 ms 4832 KB Output is correct
2 Correct 17399 ms 5444 KB Output is correct
3 Correct 16554 ms 4956 KB Output is correct
4 Correct 16583 ms 4956 KB Output is correct
5 Correct 16450 ms 4972 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Execution timed out 20047 ms 4984 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 16548 KB Output is correct
2 Correct 1287 ms 16496 KB Output is correct
3 Correct 603 ms 16620 KB Output is correct
4 Correct 655 ms 17856 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16481 ms 4716 KB Output is correct
2 Correct 17461 ms 5024 KB Output is correct
3 Correct 16622 ms 4972 KB Output is correct
4 Correct 16563 ms 4956 KB Output is correct
5 Correct 16355 ms 4972 KB Output is correct
6 Correct 606 ms 16492 KB Output is correct
7 Correct 1270 ms 16492 KB Output is correct
8 Correct 612 ms 16620 KB Output is correct
9 Correct 646 ms 17772 KB Output is correct
10 Correct 86 ms 8428 KB Output is correct
11 Correct 85 ms 8428 KB Output is correct
12 Correct 163 ms 11116 KB Output is correct
13 Correct 86 ms 8428 KB Output is correct
14 Correct 86 ms 8428 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 2 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 2 ms 492 KB Output is correct
23 Correct 2 ms 492 KB Output is correct
24 Correct 2 ms 492 KB Output is correct
25 Correct 82 ms 2796 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Execution timed out 20093 ms 5108 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16470 ms 4844 KB Output is correct
2 Correct 17387 ms 5544 KB Output is correct
3 Correct 16630 ms 4956 KB Output is correct
4 Correct 16494 ms 4972 KB Output is correct
5 Correct 16349 ms 4912 KB Output is correct
6 Correct 599 ms 16492 KB Output is correct
7 Correct 1280 ms 16488 KB Output is correct
8 Correct 603 ms 16492 KB Output is correct
9 Correct 645 ms 17900 KB Output is correct
10 Correct 85 ms 8428 KB Output is correct
11 Correct 86 ms 8428 KB Output is correct
12 Correct 165 ms 11116 KB Output is correct
13 Correct 82 ms 8428 KB Output is correct
14 Correct 85 ms 8428 KB Output is correct
15 Runtime error 365 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -