oj.uz

Submission #351232

# Submission time Handle Problem Language Result Execution time Memory
351232 2021-01-19T16:52:15 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;
bool*** mark;
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++ ) {
			mark[col][i][j] = false;
			cost[col][i][j] = INT_MAX;
		}
	priority_queue<path> heap;
	cost[col][0][col] = 0;
	heap.push(path(0,col,0));
	while(!heap.empty()) {
		path p = heap.top();
		heap.pop();
		int r = p.r;
		int c = p.c;
		if(mark[col][r][c])
			continue;
		mark[col][r][c] = true;
		int dist = p.dist;
		if(c >= 1 && dist+edgeH[r][c-1] < cost[col][r][c-1]) {
			cost[col][r][c-1] = dist+edgeH[r][c-1];
			heap.push(path(r,c-1,dist+edgeH[r][c-1]));
		}
		if(c < m-1 && dist+edgeH[r][c] < cost[col][r][c+1]) {
			cost[col][r][c+1] = dist+edgeH[r][c];
			heap.push(path(r,c+1,dist+edgeH[r][c]));
		}
		if(r < n-1 && dist+edgeV[r][c] < cost[col][r+1][c]) {
			cost[col][r+1][c] = dist+edgeV[r][c];
			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];
	mark = new bool**[m];
	for( int col = 0 ; col < m ; col++ ) {
		cost[col] = new int*[n];
		mark[col] = new bool*[n];
		for( int i = 0 ; i < n ; i++ ) {
			cost[col][i] = new int[m];
			mark[col][i] = new bool[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 113 ms 8556 KB Output is correct
2 Correct 91 ms 8684 KB Output is correct
3 Correct 169 ms 10220 KB Output is correct
4 Correct 90 ms 8556 KB Output is correct
5 Correct 89 ms 8556 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 1 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 82 ms 1516 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12421 ms 5920 KB Output is correct
2 Correct 16986 ms 6216 KB Output is correct
3 Correct 12569 ms 6052 KB Output is correct
4 Correct 12494 ms 6124 KB Output is correct
5 Correct 12348 ms 6000 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Execution timed out 20088 ms 6124 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 16808 KB Output is correct
2 Correct 1308 ms 16748 KB Output is correct
3 Correct 497 ms 16748 KB Output is correct
4 Correct 543 ms 17900 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12570 ms 5996 KB Output is correct
2 Correct 17205 ms 6300 KB Output is correct
3 Correct 12771 ms 6124 KB Output is correct
4 Correct 12747 ms 6052 KB Output is correct
5 Correct 12403 ms 6000 KB Output is correct
6 Correct 527 ms 16936 KB Output is correct
7 Correct 1317 ms 16876 KB Output is correct
8 Correct 543 ms 16808 KB Output is correct
9 Correct 543 ms 17528 KB Output is correct
10 Correct 89 ms 8684 KB Output is correct
11 Correct 88 ms 8556 KB Output is correct
12 Correct 170 ms 10220 KB Output is correct
13 Correct 90 ms 8556 KB Output is correct
14 Correct 90 ms 8556 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 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 1 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 84 ms 1516 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Execution timed out 20060 ms 6124 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12331 ms 6124 KB Output is correct
2 Correct 16903 ms 6168 KB Output is correct
3 Correct 12531 ms 6052 KB Output is correct
4 Correct 12583 ms 6052 KB Output is correct
5 Correct 12259 ms 6000 KB Output is correct
6 Correct 497 ms 16876 KB Output is correct
7 Correct 1326 ms 16876 KB Output is correct
8 Correct 493 ms 16748 KB Output is correct
9 Correct 541 ms 17644 KB Output is correct
10 Correct 89 ms 8556 KB Output is correct
11 Correct 89 ms 8556 KB Output is correct
12 Correct 168 ms 10220 KB Output is correct
13 Correct 89 ms 8556 KB Output is correct
14 Correct 89 ms 8556 KB Output is correct
15 Runtime error 376 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -