oj.uz

Submission #60256

# Submission time Handle Problem Language Result Execution time Memory
60256 2018-07-23T22:51:30 Z ksun48 Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 263168 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<vector<int> > Paths;
const int MAXD = 100000000; // 1e8

int r;
int c;

vector<vector<int> > h;
vector<vector<int> > v;

void pr(const Paths &ans){
	for(int i = 0; i < c; i++){
		for(int j = 0; j < c; j++){
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void dnc(const Paths &a, const Paths &b, Paths &paths, int t, int bl, int br, int ml, int mr){
	if(bl > br) return;
	// top, bottom left, bottom right
	int bm = (bl + br) / 2;
	int best = MAXD + 1;
	int bestm = -1;
	for(int m = ml; m <= mr; m++){
		int dist = a[t][m] + b[m][bm];
		if(dist < best){
			best = dist;
			bestm = m;
		}
	}
	assert(bestm != -1);
	paths[t][bm] = best;
	dnc(a, b, paths, t, bl, bm - 1, ml, bestm);
	dnc(a, b, paths, t, bm + 1, br, bestm, mr);
}

Paths join(const Paths &a, const Paths &b){
	Paths paths(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		dnc(a, b, paths, i, 0, c-1, 0, c-1);
	}
	return paths;
}

Paths horizontal(int row){
	vector<int> psums(c);
	psums[0] = 0;
	for(int i = 1; i < c; i++){
		psums[i] = psums[i-1] + h[row][i-1];
	}
	Paths paths(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		for(int j = 0; j < c; j++){
			paths[i][j] = abs(psums[j] - psums[i]);
		}
	}
	return paths;
}

Paths empty(){
	Paths p2(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		p2[i][i] = 0;
	}
	return p2;
}

Paths make(int row){
	Paths p2(c, vector<int>(c, MAXD));
	for(int i = 0; i < c; i++){
		p2[i][i] = v[row][i];
	}
	return join(horizontal(row), join(p2, horizontal(row + 1)));
}

Paths ans;
int updated = 0;

void compute(){
	ans = empty();
	for(int i = 0; i + 1 < r; i++){
		ans = join(ans, make(i));
	}
	updated = 1;
}

struct node {
	Paths p;
	node *l, *r;
	int lx, rx;
};

node* build(int lx, int rx){
	node* a = new node();
	a->lx = lx;
	a->rx = rx;
	if(lx == rx){
		a->l = a->r = NULL;
		a->p = make(lx);
	} else {
		int mx = (lx + rx) / 2;
		a->l = build(lx, mx);
		a->r = build(mx + 1, rx);
		a->p = join(a->l->p, a->r->p);
	}
	return a;
}

void upd(node* v, int x){
	if(x < v->lx || x > v->rx) return;
	if(v->lx == x && v->rx == x){
		v->p = make(x);
	} else {
		upd(v->l, x);
		upd(v->r, x);
		v->p = join(v->l->p, v->r->p);
	}
}

node* tree;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R;
	c = C;
	h.resize(r, vector<int>(c-1, 0));
	v.resize(r-1, vector<int>(c, 0));
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c-1; j++){
			h[i][j] = H[i][j];
		}
	}
	for(int i = 0; i < r-1; i++){
		for(int j = 0; j < c; j++){
			v[i][j] = V[i][j];
		}
	}
	compute();
	tree = build(0, r-2);
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	updated = 0;
	upd(tree, P-1);
	upd(tree, P);
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	updated = 0;
	upd(tree, P);
}

int escape(int V1, int V2) {
	if(!updated){
		compute();
	}
	return tree->p[V1][V2];
	return ans[V1][V2];
}

Compilation message

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2291 ms 5948 KB Output is correct
2 Correct 2502 ms 5992 KB Output is correct
3 Correct 2592 ms 7836 KB Output is correct
4 Correct 2526 ms 7836 KB Output is correct
5 Correct 2899 ms 7836 KB Output is correct
6 Correct 3 ms 7836 KB Output is correct
7 Correct 3 ms 7836 KB Output is correct
8 Correct 2 ms 7836 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7836 KB Output is correct
2 Correct 3 ms 7836 KB Output is correct
3 Correct 3 ms 7836 KB Output is correct
4 Correct 4 ms 7836 KB Output is correct
5 Correct 5 ms 7836 KB Output is correct
6 Correct 6 ms 7836 KB Output is correct
7 Correct 6 ms 7836 KB Output is correct
8 Correct 4 ms 7836 KB Output is correct
9 Correct 33 ms 7836 KB Output is correct
10 Correct 4 ms 7836 KB Output is correct
11 Correct 84 ms 7836 KB Output is correct
12 Correct 4 ms 7836 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 9792 KB Output is correct
2 Correct 5222 ms 9792 KB Output is correct
3 Correct 6819 ms 9796 KB Output is correct
4 Correct 6168 ms 9796 KB Output is correct
5 Correct 6057 ms 9796 KB Output is correct
6 Correct 2 ms 9796 KB Output is correct
7 Correct 2 ms 9796 KB Output is correct
8 Correct 2 ms 9796 KB Output is correct
9 Correct 4108 ms 9796 KB Output is correct
10 Correct 2 ms 9796 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3879 ms 10896 KB Output is correct
2 Correct 3805 ms 10896 KB Output is correct
3 Correct 3950 ms 10900 KB Output is correct
4 Correct 4022 ms 11748 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1155 ms 11748 KB Output is correct
2 Correct 4559 ms 11748 KB Output is correct
3 Correct 6639 ms 11748 KB Output is correct
4 Correct 6688 ms 11748 KB Output is correct
5 Correct 6042 ms 11748 KB Output is correct
6 Correct 3873 ms 11748 KB Output is correct
7 Correct 3475 ms 11748 KB Output is correct
8 Correct 3641 ms 11748 KB Output is correct
9 Correct 3607 ms 11748 KB Output is correct
10 Correct 2533 ms 11748 KB Output is correct
11 Correct 2288 ms 11748 KB Output is correct
12 Correct 2413 ms 11748 KB Output is correct
13 Correct 2348 ms 11748 KB Output is correct
14 Correct 2314 ms 11748 KB Output is correct
15 Correct 2 ms 11748 KB Output is correct
16 Correct 2 ms 11748 KB Output is correct
17 Correct 2 ms 11748 KB Output is correct
18 Correct 5 ms 11748 KB Output is correct
19 Correct 4 ms 11748 KB Output is correct
20 Correct 5 ms 11748 KB Output is correct
21 Correct 4 ms 11748 KB Output is correct
22 Correct 5 ms 11748 KB Output is correct
23 Correct 4 ms 11748 KB Output is correct
24 Correct 5 ms 11748 KB Output is correct
25 Correct 99 ms 11748 KB Output is correct
26 Correct 5 ms 11748 KB Output is correct
27 Correct 5207 ms 11748 KB Output is correct
28 Execution timed out 20080 ms 263168 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1391 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -