Submission #58709

#	Time	Username	Problem	Language	Result	Execution time	Memory
58709		kingpig9	Wombats (IOI13_wombats)	C++11	100 / 100	9158 ms	207008 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5003;
const int MAXM = 203;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N, M;
int H[MAXN][MAXM], V[MAXN][MAXM];

struct node {
	int path[MAXM][MAXM];

	int* operator[] (int x) {
		return path[x];
	}

	const int* operator[] (int x) const {
		return path[x];
	}
};

int opt[MAXN][MAXM];

node operator + (const node &a, const node &b) {
	node res;
	fillchar(res.path, 63);

	//opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
	//this is the KEY OBSERVATION

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < M; j++) {
			if (res[0][i] > a[0][j] + b[j][i]) {
				res[0][i] = a[0][j] + b[j][i];
				opt[0][i] = j;
			}
		}
	}

	//ok now let's do this
	for (int i = 1; i < M; i++) {
		//res[i][j] compute
		//opt[i - 1][j] <= opt[i][j] <= opt[i][j + 1]
		//for this reason it is better to do it in decreasing j
		opt[i][M] = M - 1;
		for (int j = M - 1; j >= 0; j--) {
			for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
				if (res[i][j] > a[i][k] + b[k][j]) {
					res[i][j] = a[i][k] + b[k][j];
					opt[i][j] = k;
				}
			}
		}
	}
	return res;
}

struct segtree {
	//so after all we need 512 * 2 = 1024
	node tree[1 << 10];
	node tmp[10];

	void make (int cur, int a, int b) {
		for (int r = a; r < b; r++) {
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < M; j++) {
					tmp[r - a][i][j] = V[r][j] + abs(H[r][i] - H[r][j]);
				}
			}
		}

		tree[cur] = tmp[0];
		for (int i = 1; i < b - a; i++) {
			tree[cur] = tree[cur] + tmp[i];
		}
	}

	void update (int r, int cur, int lt, int rt) {
		if (rt - lt <= 10) {
			make(cur, lt, rt);
			return;
		}

		int mid = (lt + rt) / 2;
		if (r < mid) {
			update(r, 2 * cur, lt, mid);
		} else {
			update(r, 2 * cur + 1, mid, rt);
		}
		tree[cur] = tree[2 * cur] + tree[2 * cur + 1];
	}

	void init (int cur, int lt, int rt) {
		if (rt - lt <= 10) {
			make(cur, lt, rt);
			return;
		}

		int mid = (lt + rt) / 2;
		init(2 * cur, lt, mid);
		init(2 * cur + 1, mid, rt);
		tree[cur] = tree[2 * cur] + tree[2 * cur + 1];
	}
} seg;

void init (int nnn, int mmm, int hhh[5000][200], int vvv[5000][200]) {
	N = nnn;
	M = mmm;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 1; j++) {
			H[i][j + 1] = H[i][j] + hhh[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			V[i][j] = vvv[i][j];
		}
	}

	//optimal paths never cross over each other!
	//KEY OBSERVATION!!!!
	seg.init(1, 0, N);
}

void changeH (int x, int y, int w) {
	int diff = w - (H[x][y + 1] - H[x][y]);
	for (int i = y + 1; i < M; i++) {
		H[x][i] += diff;
	}
	seg.update(x, 1, 0, N);
}

void changeV (int x, int y, int w) {
	V[x][y] = w;
	seg.update(x, 1, 0, N);
}

int escape (int v1, int v2) {
	return seg.tree[1][v1][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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24