oj.uz

Submission #351212

# Submission time Handle Problem Language Result Execution time Memory
351212 2021-01-19T16:28:36 Z Mefarnis Wombats (IOI13_wombats) C++14
9 / 100
 20000 ms 16760 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;
		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 85 ms 8428 KB Output is correct
2 Correct 85 ms 8428 KB Output is correct
3 Correct 162 ms 11500 KB Output is correct
4 Correct 85 ms 8556 KB Output is correct
5 Correct 86 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
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 Incorrect 2 ms 492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20096 ms 4992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20064 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20061 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -