oj.uz

Submission #235311

# Submission time Handle Problem Language Result Execution time Memory
235311 2020-05-27T17:03:50 Z crossing0ver Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 69704 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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 116 ms 51704 KB Output is correct
2 Correct 118 ms 51704 KB Output is correct
3 Correct 210 ms 54520 KB Output is correct
4 Correct 117 ms 51712 KB Output is correct
5 Correct 117 ms 51792 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 256 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 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 94 ms 2936 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 940 ms 1656 KB Output is correct
2 Correct 13821 ms 1984 KB Output is correct
3 Correct 9790 ms 1664 KB Output is correct
4 Correct 10743 ms 1736 KB Output is correct
5 Correct 10075 ms 1664 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
9 Correct 6196 ms 1664 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 55804 KB Output is correct
2 Correct 1628 ms 55928 KB Output is correct
3 Correct 763 ms 55928 KB Output is correct
4 Correct 854 ms 57208 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 955 ms 1656 KB Output is correct
2 Correct 13899 ms 1864 KB Output is correct
3 Correct 9756 ms 1784 KB Output is correct
4 Correct 10697 ms 1724 KB Output is correct
5 Correct 10131 ms 1800 KB Output is correct
6 Correct 774 ms 55928 KB Output is correct
7 Correct 1576 ms 55928 KB Output is correct
8 Correct 768 ms 55928 KB Output is correct
9 Correct 821 ms 57180 KB Output is correct
10 Correct 117 ms 51884 KB Output is correct
11 Correct 117 ms 51840 KB Output is correct
12 Correct 203 ms 54648 KB Output is correct
13 Correct 116 ms 51712 KB Output is correct
14 Correct 116 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 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 7 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 91 ms 2940 KB Output is correct
26 Correct 6 ms 640 KB Output is correct
27 Correct 6300 ms 1756 KB Output is correct
28 Execution timed out 20033 ms 61604 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 1784 KB Output is correct
2 Correct 13882 ms 1860 KB Output is correct
3 Correct 9771 ms 1912 KB Output is correct
4 Correct 10679 ms 1816 KB Output is correct
5 Correct 10130 ms 1732 KB Output is correct
6 Correct 763 ms 55800 KB Output is correct
7 Correct 1612 ms 55800 KB Output is correct
8 Correct 807 ms 55776 KB Output is correct
9 Correct 818 ms 57104 KB Output is correct
10 Correct 119 ms 51832 KB Output is correct
11 Correct 116 ms 51832 KB Output is correct
12 Correct 202 ms 54520 KB Output is correct
13 Correct 119 ms 51832 KB Output is correct
14 Correct 116 ms 51704 KB Output is correct
15 Execution timed out 20022 ms 69704 KB Time limit exceeded
16 Halted 0 ms 0 KB -