oj.uz

Submission #351225

# Submission time Handle Problem Language Result Execution time Memory
351225 2021-01-19T16:47:45 Z Mefarnis Wombats (IOI13_wombats) C++14
18 / 100
 1394 ms 17644 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[n][m])
			continue;
		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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8556 KB Output is correct
2 Correct 87 ms 8556 KB Output is correct
3 Correct 160 ms 10220 KB Output is correct
4 Correct 84 ms 8604 KB Output is correct
5 Correct 86 ms 8556 KB Output is correct
6 Runtime error 2 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 5996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 16936 KB Output is correct
2 Correct 1394 ms 17004 KB Output is correct
3 Correct 479 ms 16808 KB Output is correct
4 Correct 522 ms 17644 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 290 ms 5996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 292 ms 5996 KB Output isn't correct
2 Halted 0 ms 0 KB -