oj.uz

답안 #60267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60267 2018-07-23T23:27:58 Z ksun48 웜뱃 (IOI13_wombats) C++14
76 / 100
 20000 ms 186284 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), p2);
}

Paths make_interval(int r1, int r2){
	Paths p = empty();
	for(int a = r1; a <= r2; a++){
		p = join(p, make(a));
	}
	return p;
}

Paths ans;

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

const int BLOCKSZ = 10;

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

void upd(node* v, int x){
	if(x < v->lx || x > v->rx) return;
	if(v->l == NULL && v->r == NULL){
		v->p = make_interval(v->lx, v->rx);
	} 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, 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];
		}
	}
	tree = build(0, r-1);
}

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

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

int escape(int V1, int V2) {
	return tree->p[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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 4728 KB Output is correct
2 Correct 15 ms 4836 KB Output is correct
3 Correct 110 ms 6592 KB Output is correct
4 Correct 20 ms 6592 KB Output is correct
5 Correct 15 ms 6592 KB Output is correct
6 Correct 3 ms 6592 KB Output is correct
7 Correct 2 ms 6592 KB Output is correct
8 Correct 3 ms 6592 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6592 KB Output is correct
2 Correct 2 ms 6592 KB Output is correct
3 Correct 3 ms 6592 KB Output is correct
4 Correct 3 ms 6592 KB Output is correct
5 Correct 2 ms 6592 KB Output is correct
6 Correct 4 ms 6592 KB Output is correct
7 Correct 4 ms 6592 KB Output is correct
8 Correct 4 ms 6592 KB Output is correct
9 Correct 4 ms 6592 KB Output is correct
10 Correct 3 ms 6592 KB Output is correct
11 Correct 91 ms 6592 KB Output is correct
12 Correct 3 ms 6592 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 763 ms 6592 KB Output is correct
2 Correct 408 ms 6592 KB Output is correct
3 Correct 923 ms 6592 KB Output is correct
4 Correct 598 ms 6592 KB Output is correct
5 Correct 704 ms 6592 KB Output is correct
6 Correct 2 ms 6592 KB Output is correct
7 Correct 2 ms 6592 KB Output is correct
8 Correct 3 ms 6592 KB Output is correct
9 Correct 3955 ms 6592 KB Output is correct
10 Correct 3 ms 6592 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 9116 KB Output is correct
2 Correct 32 ms 9132 KB Output is correct
3 Correct 38 ms 9148 KB Output is correct
4 Correct 80 ms 9900 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 796 ms 9900 KB Output is correct
2 Correct 508 ms 9900 KB Output is correct
3 Correct 1288 ms 9900 KB Output is correct
4 Correct 692 ms 9900 KB Output is correct
5 Correct 720 ms 9900 KB Output is correct
6 Correct 24 ms 9900 KB Output is correct
7 Correct 21 ms 9900 KB Output is correct
8 Correct 24 ms 9900 KB Output is correct
9 Correct 66 ms 9916 KB Output is correct
10 Correct 14 ms 9916 KB Output is correct
11 Correct 15 ms 9916 KB Output is correct
12 Correct 97 ms 9916 KB Output is correct
13 Correct 16 ms 9916 KB Output is correct
14 Correct 15 ms 9916 KB Output is correct
15 Correct 3 ms 9916 KB Output is correct
16 Correct 3 ms 9916 KB Output is correct
17 Correct 3 ms 9916 KB Output is correct
18 Correct 3 ms 9916 KB Output is correct
19 Correct 4 ms 9916 KB Output is correct
20 Correct 4 ms 9916 KB Output is correct
21 Correct 3 ms 9916 KB Output is correct
22 Correct 4 ms 9916 KB Output is correct
23 Correct 6 ms 9916 KB Output is correct
24 Correct 3 ms 9916 KB Output is correct
25 Correct 94 ms 9916 KB Output is correct
26 Correct 3 ms 9916 KB Output is correct
27 Correct 4057 ms 9916 KB Output is correct
28 Correct 9641 ms 57576 KB Output is correct
29 Correct 8145 ms 57576 KB Output is correct
30 Correct 8166 ms 57576 KB Output is correct
31 Correct 8895 ms 58712 KB Output is correct
32 Correct 3 ms 58712 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 897 ms 58712 KB Output is correct
2 Correct 512 ms 58712 KB Output is correct
3 Correct 1034 ms 58712 KB Output is correct
4 Correct 556 ms 58712 KB Output is correct
5 Correct 787 ms 58712 KB Output is correct
6 Correct 29 ms 58712 KB Output is correct
7 Correct 24 ms 58712 KB Output is correct
8 Correct 28 ms 58712 KB Output is correct
9 Correct 81 ms 58712 KB Output is correct
10 Correct 17 ms 58712 KB Output is correct
11 Correct 23 ms 58712 KB Output is correct
12 Correct 98 ms 58712 KB Output is correct
13 Correct 17 ms 58712 KB Output is correct
14 Correct 15 ms 58712 KB Output is correct
15 Correct 13371 ms 185984 KB Output is correct
16 Execution timed out 20079 ms 186284 KB Time limit exceeded
17 Halted 0 ms 0 KB -