oj.uz

Submission #235242

# Submission time Handle Problem Language Result Execution time Memory
235242 2020-05-27T13:27:52 Z crossing0ver Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 69804 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() {
	while (!pq.empty())
	pq.pop();
	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;
			if (X == R - 1) {
				D[i][Y] = val;
			}
			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} } );
				}
			}
		}
	}
}
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];
	}
	//dijkstra();
}
void changeH(int P, int Q, int W) {
	G[P][Q][0] = W;
	G[P][Q+1][1] = W;
//	dijkstra();
flag = 0;
}

void changeV(int P, int Q, int W) {
    G[P][Q][2] = W;
//    dijkstra();
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 125 ms 51832 KB Output is correct
2 Correct 126 ms 51712 KB Output is correct
3 Correct 205 ms 53344 KB Output is correct
4 Correct 126 ms 51712 KB Output is correct
5 Correct 127 ms 51704 KB Output is correct
6 Correct 5 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 5 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 5 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 6 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 1708 KB Output is correct
2 Correct 14240 ms 1788 KB Output is correct
3 Correct 10176 ms 1732 KB Output is correct
4 Correct 11010 ms 1728 KB Output is correct
5 Correct 10434 ms 1784 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6353 ms 1796 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 766 ms 55672 KB Output is correct
2 Correct 1609 ms 55808 KB Output is correct
3 Correct 787 ms 55672 KB Output is correct
4 Correct 828 ms 56568 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 1644 KB Output is correct
2 Correct 14298 ms 1916 KB Output is correct
3 Correct 10145 ms 1784 KB Output is correct
4 Correct 11009 ms 1732 KB Output is correct
5 Correct 10439 ms 1784 KB Output is correct
6 Correct 794 ms 55680 KB Output is correct
7 Correct 1642 ms 55672 KB Output is correct
8 Correct 783 ms 55928 KB Output is correct
9 Correct 841 ms 57336 KB Output is correct
10 Correct 127 ms 51712 KB Output is correct
11 Correct 128 ms 51704 KB Output is correct
12 Correct 209 ms 54648 KB Output is correct
13 Correct 126 ms 51832 KB Output is correct
14 Correct 127 ms 51704 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 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 6 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 90 ms 2936 KB Output is correct
26 Correct 6 ms 640 KB Output is correct
27 Correct 6398 ms 1784 KB Output is correct
28 Execution timed out 20043 ms 61716 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 1784 KB Output is correct
2 Correct 14251 ms 1916 KB Output is correct
3 Correct 10065 ms 1724 KB Output is correct
4 Correct 11042 ms 1784 KB Output is correct
5 Correct 10480 ms 1784 KB Output is correct
6 Correct 793 ms 55672 KB Output is correct
7 Correct 1660 ms 55804 KB Output is correct
8 Correct 760 ms 55672 KB Output is correct
9 Correct 904 ms 57068 KB Output is correct
10 Correct 127 ms 51712 KB Output is correct
11 Correct 126 ms 51712 KB Output is correct
12 Correct 205 ms 54520 KB Output is correct
13 Correct 125 ms 51832 KB Output is correct
14 Correct 126 ms 51712 KB Output is correct
15 Execution timed out 20069 ms 69804 KB Time limit exceeded
16 Halted 0 ms 0 KB -