oj.uz

Submission #235245

# Submission time Handle Problem Language Result Execution time Memory
235245 2020-05-27T13:41:22 Z crossing0ver Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 59820 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#include "wombats.h"
using namespace std;
int R,C,H[5000][200],V[5000][200],vis[5000][200],help,dis[5000][2000],X,Y,x,y,G[5000][200][3],tr[5000][200],val,i,j;
pair<int,pair<int,int> > v;
bool flag;
int D[200][200];
int dx[] = {0,0,1};
int dy[] = {1,-1,0};
priority_queue<pair<int,pair<int,int > > > pq; 
void dijkstra() {
	for (i = 0; i < C; i++) {
		help++;
		pq.push ({0,{0, i}});
		tr[0][i] = help;
		dis[0][i] = 0;
		while (!pq.empty()) {
			 v = pq.top();
			 pq.pop();
			 X = v.se.fi;
			 Y = v.se.se;
			 if (vis[X][Y] == help) continue; 
			 val = -v.fi;
			vis[X][Y] = help;
			for (j = 0; j < 3; j++) {
				x = dx[j] +	X;
				y = dy[j] + Y;
				if (x >= R || y < 0 || y >= C) continue;
				if (help != tr[x][y] || dis[x][y] > val + G[X][Y][j] ) {
					tr[x][y] = help;
					dis[x][y] = val + G[X][Y][j];
					pq.push( { -dis[x][y], { x , y} } );
				}
			}
		}
		for (j = 0; j < C; j++)
			D[i][j] = dis[R-1][j];
	}
}
void init(int R1, int C1, int H1[5000][200], int V1[5000][200]) {
	R = R1; C = C1;
	for (i = 0; i < R; i++)
	for (j = 0; j < C; j++) {
		H[i][j] = H1[i][j],
		V[i][j] = V1[i][j];
	}
	for (i = 0; i < R; i++)
	for (j = 0; j < C; j++) {
		G[i][j][0] = H[i][j];
		if (j)
		G[i][j][1] = H[i][j-1];
		G[i][j][2] = V[i][j];
	}
}
void changeH(int P, int Q, int W) {
	G[P][Q][0] = W;
	G[P][Q+1][1] = W;
flag = 0;
}
void changeV(int P, int Q, int W) {
    G[P][Q][2] = W;
flag = 0;
}
int escape(int V1, int V2) {
	if (!flag) {
		flag = 1;
		dijkstra();
	}
    return D[V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 51712 KB Output is correct
2 Correct 124 ms 51704 KB Output is correct
3 Correct 207 ms 53496 KB Output is correct
4 Correct 124 ms 51704 KB Output is correct
5 Correct 124 ms 51704 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 7 ms 564 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 89 ms 1656 KB Output is correct
12 Correct 7 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 1788 KB Output is correct
2 Correct 14334 ms 2040 KB Output is correct
3 Correct 10090 ms 1712 KB Output is correct
4 Correct 10994 ms 1704 KB Output is correct
5 Correct 10308 ms 1656 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6248 ms 1760 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 55800 KB Output is correct
2 Correct 1628 ms 55672 KB Output is correct
3 Correct 788 ms 55680 KB Output is correct
4 Correct 822 ms 56696 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 1696 KB Output is correct
2 Correct 14052 ms 1852 KB Output is correct
3 Correct 10006 ms 1784 KB Output is correct
4 Correct 10938 ms 1708 KB Output is correct
5 Correct 10359 ms 1712 KB Output is correct
6 Correct 793 ms 55724 KB Output is correct
7 Correct 1621 ms 55732 KB Output is correct
8 Correct 829 ms 55672 KB Output is correct
9 Correct 835 ms 56696 KB Output is correct
10 Correct 127 ms 51712 KB Output is correct
11 Correct 123 ms 51784 KB Output is correct
12 Correct 208 ms 53368 KB Output is correct
13 Correct 124 ms 51712 KB Output is correct
14 Correct 123 ms 51712 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 6 ms 640 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 6 ms 768 KB Output is correct
23 Correct 6 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 90 ms 1656 KB Output is correct
26 Correct 6 ms 640 KB Output is correct
27 Correct 6288 ms 1788 KB Output is correct
28 Execution timed out 20063 ms 58068 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 1656 KB Output is correct
2 Correct 14117 ms 1852 KB Output is correct
3 Correct 10021 ms 1784 KB Output is correct
4 Correct 10890 ms 1656 KB Output is correct
5 Correct 10338 ms 1648 KB Output is correct
6 Correct 814 ms 55800 KB Output is correct
7 Correct 1631 ms 55748 KB Output is correct
8 Correct 778 ms 55800 KB Output is correct
9 Correct 843 ms 56544 KB Output is correct
10 Correct 124 ms 51712 KB Output is correct
11 Correct 124 ms 51712 KB Output is correct
12 Correct 202 ms 53368 KB Output is correct
13 Correct 123 ms 51712 KB Output is correct
14 Correct 126 ms 51704 KB Output is correct
15 Execution timed out 20018 ms 59820 KB Time limit exceeded
16 Halted 0 ms 0 KB -