oj.uz

Submission #1023932

# Submission time Handle Problem Language Result Execution time Memory
1023932 2024-07-15T09:43:03 Z dozer Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 25028 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 dijkstra(int 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) {
	dijkstra(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 47 ms 15964 KB Output is correct
2 Correct 47 ms 15964 KB Output is correct
3 Correct 16143 ms 18756 KB Output is correct
4 Correct 46 ms 15960 KB Output is correct
5 Correct 47 ms 15964 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 14 ms 1000 KB Output is correct
5 Correct 5 ms 856 KB Output is correct
6 Correct 5 ms 988 KB Output is correct
7 Correct 10 ms 860 KB Output is correct
8 Correct 9 ms 860 KB Output is correct
9 Correct 11 ms 976 KB Output is correct
10 Correct 10 ms 916 KB Output is correct
11 Correct 5062 ms 3160 KB Output is correct
12 Correct 11 ms 860 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 9296 KB Output is correct
2 Correct 302 ms 9292 KB Output is correct
3 Correct 190 ms 9228 KB Output is correct
4 Correct 210 ms 9408 KB Output is correct
5 Correct 184 ms 9132 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 324 ms 9392 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 23900 KB Output is correct
2 Correct 731 ms 23900 KB Output is correct
3 Correct 309 ms 23896 KB Output is correct
4 Execution timed out 20064 ms 25028 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 9244 KB Output is correct
2 Correct 321 ms 9296 KB Output is correct
3 Correct 204 ms 9432 KB Output is correct
4 Correct 183 ms 9400 KB Output is correct
5 Correct 193 ms 9296 KB Output is correct
6 Correct 313 ms 23900 KB Output is correct
7 Correct 863 ms 24144 KB Output is correct
8 Correct 325 ms 23900 KB Output is correct
9 Execution timed out 20095 ms 24972 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 9188 KB Output is correct
2 Correct 284 ms 9296 KB Output is correct
3 Correct 185 ms 9392 KB Output is correct
4 Correct 179 ms 9300 KB Output is correct
5 Correct 181 ms 9144 KB Output is correct
6 Correct 314 ms 23900 KB Output is correct
7 Correct 728 ms 24008 KB Output is correct
8 Correct 317 ms 23896 KB Output is correct
9 Execution timed out 20058 ms 24952 KB Time limit exceeded
10 Halted 0 ms 0 KB -