Submission #69878

#	Time	Username	Problem	Language	Result	Execution time	Memory
69878		FLDutchman	Wombats (IOI13_wombats)	C++14	34 / 100	20100 ms	24272 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
#define mp make_pair

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int NMAX = 1e5+10;

int H[5000][200], V[5000][200];
int R, C;

int precomp[2][2];
vvi dist;

vii adj(int r, int c){
	vii n;
	if(r < R-1) n.pb(mp(r+1 + R*c, V[r][c]));
	if(c > 0) n.pb( mp(r+R*(c-1), H[r][c-1]) );
	if(c < C-1) n.pb( mp( r+R*(c+1), H[r][c]) );
	return n;
}

void dijkstra(int r, int c){
	dist.assign(R, vi(C, 2e9));
	priority_queue<ii, vii, greater<ii>> q;
	q.push({0, r + R * c});
	//cerr<<r<<" "<<c<<endl;
	dist[r][c] = 0;
	while(!q.empty()){
		ii p = q.top(); q.pop();
		int d = p.fst, u = p.snd;
		int r = u%R, c = u/R;
		if(dist[r][c] < d) continue;
		for(ii p: adj(r, c)) {
			int v = p.fst, l = p.snd;
			//cout << l << endl;
			int &D = dist[v%R][v/R];
			if(d + l < D) {
				D = d + l;
				q.push({D, v});
			}
		}
	}
}

void recomp(){
	if(C == 2){
		dijkstra(0, 0);
		precomp[0][0] = dist[R-1][0];
		precomp[0][1] = dist[R-1][1];
		dijkstra(0, 1);
		precomp[1][0] = dist[R-1][0];
		precomp[1][1] = dist[R-1][1];
	}
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
	FOR(i, 0, r) FOR(j, 0, c) {H[i][j] = h[i][j]; V[i][j] = v[i][j];}
	R = r;
	C = c;
	dist.assign(R, vi(C, 2e9));
	recomp();
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	recomp();
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
    recomp();
}

int escape(int V1, int V2) {
	if(C == 2) {
		return precomp[V1][V2];
	}

	dijkstra(0, V1);
	/*FOR(i, 0, R) {
		FOR(j, 0, C) cout << dist[i][j] << " ";
		cout << endl;
	}*/
    return dist[R-1][V2];
}

Compilation message (stderr)

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