oj.uz

Submission #351237

# Submission time Handle Problem Language Result Execution time Memory
351237 2021-01-19T16:57:08 Z Mefarnis Wombats (IOI13_wombats) C++14
55 / 100
 1330 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]));
		}
	}
}

bool checkCond() {
	return (m <= 2) || (n <= 20 && m <= 20);
}

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];
		}
	}
	if(checkCond())
		for( int i = 0 ; i < m ; i++ )
			dijkstra(i);
}

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

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

int escape(int V1, int V2) {
	int ans;
	if(checkCond())
		ans = cost[V1][n-1][V2];
	else {
		dijkstra(V1);
		ans = cost[V1][n-1][V2];
	}
	return ans;
}

/*
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 90 ms 8556 KB Output is correct
2 Correct 90 ms 8684 KB Output is correct
3 Correct 174 ms 10220 KB Output is correct
4 Correct 98 ms 8556 KB Output is correct
5 Correct 93 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 0 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 3 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 79 ms 1516 KB Output is correct
12 Correct 2 ms 492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 6000 KB Output is correct
2 Correct 175 ms 6096 KB Output is correct
3 Correct 138 ms 5996 KB Output is correct
4 Correct 140 ms 6052 KB Output is correct
5 Correct 132 ms 5996 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 Correct 197 ms 5996 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 16748 KB Output is correct
2 Correct 1317 ms 16768 KB Output is correct
3 Correct 499 ms 16808 KB Output is correct
4 Correct 553 ms 17624 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 5996 KB Output is correct
2 Correct 177 ms 6096 KB Output is correct
3 Correct 130 ms 5996 KB Output is correct
4 Correct 130 ms 5996 KB Output is correct
5 Correct 129 ms 6124 KB Output is correct
6 Correct 496 ms 16812 KB Output is correct
7 Correct 1319 ms 16820 KB Output is correct
8 Correct 494 ms 16936 KB Output is correct
9 Correct 543 ms 17644 KB Output is correct
10 Correct 89 ms 8556 KB Output is correct
11 Correct 91 ms 8684 KB Output is correct
12 Correct 168 ms 10348 KB Output is correct
13 Correct 91 ms 8556 KB Output is correct
14 Correct 91 ms 8556 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 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 78 ms 1516 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 197 ms 6124 KB Output is correct
28 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 6092 KB Output is correct
2 Correct 174 ms 6096 KB Output is correct
3 Correct 129 ms 5996 KB Output is correct
4 Correct 132 ms 6052 KB Output is correct
5 Correct 130 ms 6024 KB Output is correct
6 Correct 488 ms 16748 KB Output is correct
7 Correct 1330 ms 16876 KB Output is correct
8 Correct 499 ms 16876 KB Output is correct
9 Correct 547 ms 17608 KB Output is correct
10 Correct 91 ms 8684 KB Output is correct
11 Correct 89 ms 8556 KB Output is correct
12 Correct 174 ms 10220 KB Output is correct
13 Correct 89 ms 8556 KB Output is correct
14 Correct 89 ms 8604 KB Output is correct
15 Runtime error 342 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -