답안 #16105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16105 2015-08-16T04:20:26 Z gs14004 웜뱃 (IOI13_wombats) C++14
100 / 100
7343 ms 191616 KB
#include "wombats.h"
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

struct node{
	int adj[205][205];
};

int a[5000][200], b[5000][200];
int n, m;
int opt[205][205];

node merge(node& a, node& b){
	node c;
	memset(c.adj,0x3f,sizeof(c.adj));
	// opt(i-1, j) <= opt(i,j) <= opt(i,j+1)
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			if(c.adj[0][i] > a.adj[0][j] + b.adj[j][i]){
				c.adj[0][i] = a.adj[0][j] + b.adj[j][i];
				opt[0][i] = j;
			}
		}
	}
	for(int i=1; i<m; i++){
		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(c.adj[i][j] > a.adj[i][k] + b.adj[k][j]){
					c.adj[i][j] = a.adj[i][k] + b.adj[k][j];
					opt[i][j] = k;
				}
			}
		}
	}
	return c;
}

node tmp[11];
struct seg{
	node tree[1050];
	void remake(int s, int e, int p){
		for(int i=s; i<=e; i++){
			for(int j=0; j<m; j++){
				for(int k=0; k<m; k++){
					tmp[i-s].adj[j][k] = b[i][k] + abs((j ? a[i][j-1] : 0) - (k ? a[i][k-1] : 0));
				}
			}
		}
		tree[p] = tmp[0];
		for(int i=1; i<=e-s; i++){
			tree[p] = merge(tree[p], tmp[i]);
		}
	}
	void add(int pos, int ps, int pe, int p){
		if(pe - ps <= 10){
			remake(ps, pe, p);
			return;
		}
		int pm = (ps + pe) / 2;
		if(pos <= pm) add(pos, ps, pm, 2*p);
		else add(pos, pm+1, pe, 2*p+1);
		tree[p] = merge(tree[2*p], tree[2*p+1]);
	}
	void init(int ps, int pe, int p){
		if(pe - ps <= 10){
			remake(ps, pe, p);
			return;
		}
		int pm = (ps + pe) / 2;
		init(ps, pm, 2*p);
		init(pm+1, pe, 2*p+1);
		tree[p] = merge(tree[2*p], tree[2*p+1]);
	}
}seg;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	n = R, m = C;
	for(int i=0; i<R; i++){
		for(int j=0; j<C; j++){
			a[i][j] = H[i][j] + (j ? a[i][j-1] : 0);
			b[i][j] = V[i][j];
		}
	}
	seg.init(0,n-1,1);
}

void changeH(int P, int Q, int W) {
    int diff = W - (a[P][Q] - (Q ? a[P][Q-1] : 0));
    for(int i=Q; i<m; i++){
    	a[P][i] += diff;
	}
    seg.add(P,0,n-1,1); 
}

void changeV(int P, int Q, int W) {
	b[P][Q] = W;
	seg.add(P,0,n-1,1);
}

int escape(int V1, int V2) {
	return seg.tree[1].adj[V1][V2];
}
# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 191444 KB Output is correct - 505 tokens
2 Correct 419 ms 191448 KB Output is correct - 505 tokens
3 Correct 483 ms 191452 KB Output is correct - 200005 tokens
4 Correct 397 ms 191452 KB Output is correct - 505 tokens
5 Correct 374 ms 191444 KB Output is correct - 505 tokens
6 Correct 0 ms 191120 KB Output is correct - 6 tokens
7 Correct 0 ms 191116 KB Output is correct - 6 tokens
8 Correct 0 ms 191116 KB Output is correct - 6 tokens
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 191116 KB Output is correct - 6 tokens
2 Correct 0 ms 191124 KB Output is correct - 6 tokens
3 Correct 0 ms 191116 KB Output is correct - 6 tokens
4 Correct 0 ms 191120 KB Output is correct - 405 tokens
5 Correct 0 ms 191116 KB Output is correct - 405 tokens
6 Correct 0 ms 191124 KB Output is correct - 405 tokens
7 Correct 0 ms 191120 KB Output is correct - 405 tokens
8 Correct 0 ms 191116 KB Output is correct - 366 tokens
9 Correct 0 ms 191120 KB Output is correct - 405 tokens
10 Correct 3 ms 191120 KB Output is correct - 366 tokens
11 Correct 88 ms 191116 KB Output is correct - 200005 tokens
12 Correct 0 ms 191120 KB Output is correct - 405 tokens
# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 191284 KB Output is correct - 105 tokens
2 Correct 137 ms 191280 KB Output is correct - 105 tokens
3 Correct 173 ms 191288 KB Output is correct - 105 tokens
4 Correct 167 ms 191284 KB Output is correct - 105 tokens
5 Correct 177 ms 191284 KB Output is correct - 105 tokens
6 Correct 0 ms 191120 KB Output is correct - 6 tokens
7 Correct 0 ms 191120 KB Output is correct - 6 tokens
8 Correct 0 ms 191116 KB Output is correct - 6 tokens
9 Correct 594 ms 191280 KB Output is correct - 105 tokens
10 Correct 0 ms 191120 KB Output is correct - 8 tokens
# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 191452 KB Output is correct - 1005 tokens
2 Correct 378 ms 191448 KB Output is correct - 1005 tokens
3 Correct 404 ms 191616 KB Output is correct - 1005 tokens
4 Correct 446 ms 191444 KB Output is correct - 100005 tokens
# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 191284 KB Output is correct - 105 tokens
2 Correct 139 ms 191284 KB Output is correct - 105 tokens
3 Correct 167 ms 191284 KB Output is correct - 105 tokens
4 Correct 170 ms 191280 KB Output is correct - 105 tokens
5 Correct 164 ms 191280 KB Output is correct - 105 tokens
6 Correct 393 ms 191452 KB Output is correct - 1005 tokens
7 Correct 389 ms 191452 KB Output is correct - 1005 tokens
8 Correct 421 ms 191616 KB Output is correct - 1005 tokens
9 Correct 440 ms 191448 KB Output is correct - 100005 tokens
10 Correct 395 ms 191444 KB Output is correct - 505 tokens
11 Correct 376 ms 191444 KB Output is correct - 505 tokens
12 Correct 484 ms 191452 KB Output is correct - 200005 tokens
13 Correct 389 ms 191448 KB Output is correct - 505 tokens
14 Correct 389 ms 191448 KB Output is correct - 505 tokens
15 Correct 0 ms 191124 KB Output is correct - 6 tokens
16 Correct 0 ms 191120 KB Output is correct - 6 tokens
17 Correct 0 ms 191116 KB Output is correct - 6 tokens
18 Correct 3 ms 191120 KB Output is correct - 405 tokens
19 Correct 0 ms 191120 KB Output is correct - 405 tokens
20 Correct 0 ms 191116 KB Output is correct - 405 tokens
21 Correct 0 ms 191124 KB Output is correct - 405 tokens
22 Correct 0 ms 191120 KB Output is correct - 366 tokens
23 Correct 0 ms 191120 KB Output is correct - 405 tokens
24 Correct 0 ms 191120 KB Output is correct - 366 tokens
25 Correct 93 ms 191120 KB Output is correct - 200005 tokens
26 Correct 0 ms 191116 KB Output is correct - 405 tokens
27 Correct 590 ms 191280 KB Output is correct - 105 tokens
28 Correct 1911 ms 191452 KB Output is correct - 50005 tokens
29 Correct 2056 ms 191444 KB Output is correct - 50005 tokens
30 Correct 2061 ms 191444 KB Output is correct - 50005 tokens
31 Correct 2040 ms 191448 KB Output is correct - 200005 tokens
32 Correct 0 ms 191120 KB Output is correct - 8 tokens
# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 191284 KB Output is correct - 105 tokens
2 Correct 133 ms 191284 KB Output is correct - 105 tokens
3 Correct 168 ms 191288 KB Output is correct - 105 tokens
4 Correct 174 ms 191284 KB Output is correct - 105 tokens
5 Correct 160 ms 191284 KB Output is correct - 105 tokens
6 Correct 366 ms 191444 KB Output is correct - 1005 tokens
7 Correct 396 ms 191448 KB Output is correct - 1005 tokens
8 Correct 407 ms 191608 KB Output is correct - 1005 tokens
9 Correct 440 ms 191448 KB Output is correct - 100005 tokens
10 Correct 383 ms 191448 KB Output is correct - 505 tokens
11 Correct 381 ms 191452 KB Output is correct - 505 tokens
12 Correct 461 ms 191448 KB Output is correct - 200005 tokens
13 Correct 389 ms 191448 KB Output is correct - 505 tokens
14 Correct 374 ms 191444 KB Output is correct - 505 tokens
15 Correct 2950 ms 191452 KB Output is correct - 11 tokens
16 Correct 7343 ms 191616 KB Output is correct - 200005 tokens
17 Correct 0 ms 191120 KB Output is correct - 6 tokens
18 Correct 0 ms 191120 KB Output is correct - 6 tokens
19 Correct 0 ms 191124 KB Output is correct - 6 tokens
20 Correct 3 ms 191120 KB Output is correct - 405 tokens
21 Correct 0 ms 191120 KB Output is correct - 405 tokens
22 Correct 0 ms 191116 KB Output is correct - 405 tokens
23 Correct 0 ms 191120 KB Output is correct - 405 tokens
24 Correct 0 ms 191116 KB Output is correct - 366 tokens
25 Correct 0 ms 191120 KB Output is correct - 405 tokens
26 Correct 0 ms 191116 KB Output is correct - 366 tokens
27 Correct 90 ms 191116 KB Output is correct - 200005 tokens
28 Correct 0 ms 191116 KB Output is correct - 405 tokens
29 Correct 602 ms 191280 KB Output is correct - 105 tokens
30 Correct 1942 ms 191448 KB Output is correct - 50005 tokens
31 Correct 5980 ms 191448 KB Output is correct - 100005 tokens
32 Correct 6016 ms 191452 KB Output is correct - 100005 tokens
33 Correct 2031 ms 191448 KB Output is correct - 50005 tokens
34 Correct 6386 ms 191448 KB Output is correct - 100005 tokens
35 Correct 2038 ms 191444 KB Output is correct - 50005 tokens
36 Correct 6503 ms 191448 KB Output is correct - 100005 tokens
37 Correct 2015 ms 191448 KB Output is correct - 200005 tokens
38 Correct 6433 ms 191612 KB Output is correct - 200005 tokens
39 Correct 0 ms 191120 KB Output is correct - 8 tokens
40 Correct 6692 ms 191452 KB Output is correct - 100005 tokens