oj.uz

Submission #235244

# Submission time Handle Problem Language Result Execution time Memory
235244 2020-05-27T13:38:25 Z crossing0ver Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 59872 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;
		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 126 ms 51712 KB Output is correct
2 Correct 122 ms 51712 KB Output is correct
3 Correct 221 ms 53368 KB Output is correct
4 Correct 127 ms 51712 KB Output is correct
5 Correct 126 ms 51832 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 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 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 6 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 98 ms 1784 KB Output is correct
12 Correct 6 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 1688 KB Output is correct
2 Correct 14221 ms 1792 KB Output is correct
3 Correct 10018 ms 1648 KB Output is correct
4 Correct 10924 ms 1648 KB Output is correct
5 Correct 10337 ms 1536 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 6295 ms 1676 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 795 ms 55676 KB Output is correct
2 Correct 1618 ms 55672 KB Output is correct
3 Correct 794 ms 55672 KB Output is correct
4 Correct 848 ms 56312 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 1536 KB Output is correct
2 Correct 14192 ms 1796 KB Output is correct
3 Correct 10094 ms 1648 KB Output is correct
4 Correct 11027 ms 1648 KB Output is correct
5 Correct 10376 ms 1656 KB Output is correct
6 Correct 770 ms 55672 KB Output is correct
7 Correct 1615 ms 55672 KB Output is correct
8 Correct 773 ms 55672 KB Output is correct
9 Correct 818 ms 56568 KB Output is correct
10 Correct 125 ms 51712 KB Output is correct
11 Correct 123 ms 51756 KB Output is correct
12 Correct 218 ms 53320 KB Output is correct
13 Correct 127 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 4 ms 384 KB Output is correct
17 Correct 5 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 640 KB Output is correct
23 Correct 6 ms 640 KB Output is correct
24 Correct 6 ms 640 KB Output is correct
25 Correct 100 ms 1656 KB Output is correct
26 Correct 6 ms 640 KB Output is correct
27 Correct 6284 ms 1656 KB Output is correct
28 Execution timed out 20056 ms 57876 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 1536 KB Output is correct
2 Correct 14104 ms 1796 KB Output is correct
3 Correct 10047 ms 1644 KB Output is correct
4 Correct 11058 ms 1644 KB Output is correct
5 Correct 10649 ms 1944 KB Output is correct
6 Correct 805 ms 55676 KB Output is correct
7 Correct 1653 ms 55680 KB Output is correct
8 Correct 797 ms 55748 KB Output is correct
9 Correct 832 ms 56696 KB Output is correct
10 Correct 124 ms 51712 KB Output is correct
11 Correct 123 ms 51712 KB Output is correct
12 Correct 243 ms 53624 KB Output is correct
13 Correct 127 ms 51712 KB Output is correct
14 Correct 126 ms 51712 KB Output is correct
15 Execution timed out 20092 ms 59872 KB Time limit exceeded
16 Halted 0 ms 0 KB -