oj.uz

Submission #1023927

# Submission time Handle Problem Language Result Execution time Memory
1023927 2024-07-15T09:38:41 Z dozer Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 262144 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define mid (l + r) / 2
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005
#define M 201

const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

static int H[5000][200];
static int V[5000][200];

int h[5000][200], v[5000][200], r, c;
int ans[200][5000][200];

void dijkstra(){
	for (int I = 0; I < c; I++){
		priority_queue<pii, vector<pii>, less<pii>> q;
		for(int i = 0; i < r; i++) for (int j = 0; j < c; j++) ans[I][i][j] = modulo;
		
		ans[I][r - 1][I] = 0;
		q.push({0, (r - 1) * M + I});
		

		while(!q.empty()){
			pii tmp = q.top();
			q.pop();
			int d = -tmp.st, x = tmp.nd / M, y = tmp.nd % M;
			if (d > ans[I][x][y]) continue;
			if (y + 1 < c){
				if (ans[I][x][y + 1] > d + h[x][y]){
					ans[I][x][y + 1] = d + h[x][y];
					q.push({-ans[I][x][y + 1], x * M + y + 1});
				}
			}

			if (y > 0){
				if (ans[I][x][y - 1] > d + h[x][y - 1]){
					ans[I][x][y - 1] = d + h[x][y - 1];
					q.push({-ans[I][x][y - 1], x * M + y - 1});
				}
			}

			if (x > 0){
				if (ans[I][x - 1][y] > d + v[x - 1][y]){
					ans[I][x - 1][y] = d + v[x - 1][y];
					q.push({-ans[I][x - 1][y], (x - 1) * M + y});
				}
			}
		}
	}
		
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R, c = C;
    for (int i = 0; i < R; i++){
    	for (int j = 0; j < C; j++){
    		h[i][j] = H[i][j], v[i][j] = V[i][j];
    		//cout<<h[i][j]<<sp<<v[i][j]<<sp;
    	}
    	//cout<<endl;
    }

    dijkstra();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    dijkstra();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    dijkstra();
}

int escape(int V1, int V2) {
    return ans[V2][0][V1];
}

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;
      |      ^~~
wombats.cpp:29:12: warning: 'V' defined but not used [-Wunused-variable]
   29 | static int V[5000][200];
      |            ^
wombats.cpp:28:12: warning: 'H' defined but not used [-Wunused-variable]
   28 | static int H[5000][200];
      |            ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 15964 KB Output is correct
2 Correct 48 ms 15964 KB Output is correct
3 Correct 88 ms 18760 KB Output is correct
4 Correct 48 ms 15960 KB Output is correct
5 Correct 48 ms 16112 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 960 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 41 ms 3268 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8617 ms 9352 KB Output is correct
2 Correct 13727 ms 9464 KB Output is correct
3 Correct 9181 ms 9304 KB Output is correct
4 Correct 9267 ms 9428 KB Output is correct
5 Correct 8693 ms 9348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 20033 ms 9304 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 23980 KB Output is correct
2 Correct 705 ms 23896 KB Output is correct
3 Correct 324 ms 23900 KB Output is correct
4 Correct 339 ms 25172 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8841 ms 9360 KB Output is correct
2 Correct 14285 ms 9368 KB Output is correct
3 Correct 8749 ms 9436 KB Output is correct
4 Correct 9093 ms 9432 KB Output is correct
5 Correct 8843 ms 9352 KB Output is correct
6 Correct 317 ms 23960 KB Output is correct
7 Correct 737 ms 23864 KB Output is correct
8 Correct 305 ms 23900 KB Output is correct
9 Correct 327 ms 25248 KB Output is correct
10 Correct 49 ms 15964 KB Output is correct
11 Correct 50 ms 15960 KB Output is correct
12 Correct 82 ms 18780 KB Output is correct
13 Correct 46 ms 15960 KB Output is correct
14 Correct 47 ms 16112 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 1 ms 964 KB Output is correct
22 Correct 1 ms 856 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 40 ms 3280 KB Output is correct
26 Correct 2 ms 856 KB Output is correct
27 Execution timed out 20091 ms 9232 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8857 ms 9556 KB Output is correct
2 Correct 14038 ms 9296 KB Output is correct
3 Correct 8796 ms 9296 KB Output is correct
4 Correct 8771 ms 9300 KB Output is correct
5 Correct 8296 ms 9344 KB Output is correct
6 Correct 302 ms 23896 KB Output is correct
7 Correct 691 ms 23972 KB Output is correct
8 Correct 305 ms 23900 KB Output is correct
9 Correct 304 ms 25172 KB Output is correct
10 Correct 46 ms 15964 KB Output is correct
11 Correct 47 ms 15964 KB Output is correct
12 Correct 82 ms 18764 KB Output is correct
13 Correct 49 ms 15960 KB Output is correct
14 Correct 46 ms 15964 KB Output is correct
15 Runtime error 4009 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -