Submission #1023927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023927		dozer	Wombats (IOI13_wombats)	C++14	39 / 100	20091 ms	262144 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24