oj.uz

답안 #67598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67598 2018-08-15T05:30:34 Z Crown 웜뱃 (IOI13_wombats) C++14
76 / 100
 19563 ms 263168 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int n, m;
const int maxn = 5005;
const int maxm = 205;
int H[maxn][maxm], V[maxn][maxm];

struct node
{
	vector< vector<int> > dist;
	node(){}
	node(bool create)
	{
		if(create)
		{
			dist.assign(m, vector<int>(m, 1e9));
			for(int i = 0; i< m; i++) dist[i][i] = 0;
		}
	}
};

node st[4*maxn];

const int ub = 5;

priority_queue< pair<int, ii> > pq;
vector< vector<int> > tod;

void dijk(int s, int r1, int r2, vector<int> &dist)
{
	tod.assign(r2-r1+1, vector<int>(m, 1e9));
	tod[0][s] = 0;
	pq.push(make_pair(0, ii(r1, s)));
	while(!pq.empty())
	{
		auto f = pq.top(); pq.pop();
		int d = -f.X, x = f.Y.X, y = f.Y.Y;
		if(d> tod[x-r1][y]) continue;
		if(y && H[x][y-1]+d< tod[x-r1][y-1])
		{
			tod[x-r1][y-1] = H[x][y-1]+d;
			pq.push(make_pair(-tod[x-r1][y-1], ii(x, y-1)));
		}
		if(y+1< m && H[x][y]+d< tod[x-r1][y+1])
		{
			tod[x-r1][y+1] = H[x][y]+d;
			pq.push(make_pair(-tod[x-r1][y+1], ii(x, y+1)));
		}
		if(x+1<= r2 && V[x][y]+d< tod[x+1-r1][y])
		{
			tod[x+1-r1][y] = V[x][y]+d;
			pq.push(make_pair(-tod[x+1-r1][y], ii(x+1, y)));
		}
	}
	dist = tod.back();
}

vector< vector<int> > opt;

void merge(vector< vector<int> > &dist, vector< vector<int> > &d1, vector< vector<int> > &d2)
{
	// printf("begun merging\n");
	opt.assign(m, vector<int>(m, 0));
	for(int diff = -m+1; diff<= m-1; diff++)
	{
		for(int i = 0; i< m; i++)
		{
			int j = i+diff;
			if(j< 0 || j>= m) continue;
			// printf("begun %d %d\n", i, j);
			dist[i][j] = 1e9;
			if(diff == -m+1)
			{
				for(int k = 0; k< m; k++)
				{
					if(d1[i][k]+d2[k][j]< dist[i][j])
					{
						dist[i][j] = d1[i][k] + d2[k][j];
						opt[i][j] = k;
					}
				}
			}
			else
			{
				for(int k = max(0, j?opt[i][j-1]:0); k<= min(m-1, i+1< m?opt[i+1][j]:m-1); k++)
				{
					//printf("k = %d\n", k);
					if(d1[i][k]+d2[k][j]< dist[i][j])
					{
						dist[i][j] = d1[i][k] + d2[k][j];
						opt[i][j] = k;
					}
				}
			}
		}
	}
	// printf("finished merging\n");
}

void build(int p = 1, int L = 0, int R = n-1)
{
	// printf("%d %d %d\n", p, L, R);
	st[p] = node(true);
	if(R-L+1<= ub)
	{
		for(int i = 0; i< m; i++)
		{
			dijk(i, L, R, st[p].dist[i]);
		}
		// printf("finished creating\n");
		return;
	}
	build(2*p, L, (L+R)/2);
	build(2*p+1, (L+R)/2, R);
	merge(st[p].dist, st[2*p].dist, st[2*p+1].dist);
}

void update(int x, int p = 1, int L = 0, int R = n-1)
{
	if(R-L+1<= ub)
	{
		for(int i = 0; i< m; i++)
		{
			dijk(i, L, R, st[p].dist[i]);
		}
		return;
	}

	int M = (L+R)/2;
	if(x<= M) update(x, 2*p, L, (L+R)/2);
	if(M<= x) update(x, 2*p+1, (L+R)/2, R);
	merge(st[p].dist, st[2*p].dist, st[2*p+1].dist);
}

void init(int R, int C, int h[5000][200], int v[5000][200])
{
	n = R, m = C;
	for(int i = 0; i< n; i++)
	{
		for(int j = 0; j+1< m; j++)
		{
			H[i][j] = h[i][j];
		}
	}
	for(int i = 0; i+1< n; i++)
	{
		for(int j = 0; j< m; j++)
		{
			V[i][j] = v[i][j];
		}
	}
	//printf("started initing\n");
	build();
}

void changeH(int P, int Q, int W)
{
	//printf("changingH\n");
	H[P][Q] = W;
	update(P);
}

void changeV(int P, int Q, int W)
{
	//printf("changingV\n");
	V[P][Q] = W;
	update(P);
}

int escape(int V1, int V2)
{
	return st[1].dist[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 11 ms 8952 KB Output is correct
2 Correct 11 ms 9116 KB Output is correct
3 Correct 88 ms 11976 KB Output is correct
4 Correct 15 ms 11976 KB Output is correct
5 Correct 13 ms 11976 KB Output is correct
6 Correct 3 ms 11976 KB Output is correct
7 Correct 3 ms 11976 KB Output is correct
8 Correct 3 ms 11976 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 624 ms 11976 KB Output is correct
2 Correct 1140 ms 11976 KB Output is correct
3 Correct 621 ms 11976 KB Output is correct
4 Correct 558 ms 11976 KB Output is correct
5 Correct 620 ms 11976 KB Output is correct
6 Correct 2 ms 11976 KB Output is correct
7 Correct 3 ms 11976 KB Output is correct
8 Correct 2 ms 11976 KB Output is correct
9 Correct 4961 ms 11976 KB Output is correct
10 Correct 2 ms 11976 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 18780 KB Output is correct
2 Correct 22 ms 18796 KB Output is correct
3 Correct 21 ms 18796 KB Output is correct
4 Correct 59 ms 19604 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 19604 KB Output is correct
2 Correct 1079 ms 19604 KB Output is correct
3 Correct 608 ms 19604 KB Output is correct
4 Correct 572 ms 19604 KB Output is correct
5 Correct 604 ms 19604 KB Output is correct
6 Correct 27 ms 19604 KB Output is correct
7 Correct 22 ms 19604 KB Output is correct
8 Correct 24 ms 19604 KB Output is correct
9 Correct 63 ms 19604 KB Output is correct
10 Correct 15 ms 19604 KB Output is correct
11 Correct 11 ms 19604 KB Output is correct
12 Correct 87 ms 19604 KB Output is correct
13 Correct 17 ms 19604 KB Output is correct
14 Correct 15 ms 19604 KB Output is correct
15 Correct 3 ms 19604 KB Output is correct
16 Correct 3 ms 19604 KB Output is correct
17 Correct 3 ms 19604 KB Output is correct
18 Correct 5 ms 19604 KB Output is correct
19 Correct 4 ms 19604 KB Output is correct
20 Correct 4 ms 19604 KB Output is correct
21 Correct 5 ms 19604 KB Output is correct
22 Correct 4 ms 19604 KB Output is correct
23 Correct 4 ms 19604 KB Output is correct
24 Correct 4 ms 19604 KB Output is correct
25 Correct 95 ms 19604 KB Output is correct
26 Correct 6 ms 19604 KB Output is correct
27 Correct 4922 ms 19604 KB Output is correct
28 Correct 16538 ms 184992 KB Output is correct
29 Correct 7887 ms 184992 KB Output is correct
30 Correct 7299 ms 184992 KB Output is correct
31 Correct 19563 ms 197576 KB Output is correct
32 Correct 4 ms 197576 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 565 ms 197576 KB Output is correct
2 Correct 1110 ms 197576 KB Output is correct
3 Correct 683 ms 197576 KB Output is correct
4 Correct 651 ms 197576 KB Output is correct
5 Correct 659 ms 197576 KB Output is correct
6 Correct 29 ms 197576 KB Output is correct
7 Correct 26 ms 197576 KB Output is correct
8 Correct 25 ms 197576 KB Output is correct
9 Correct 75 ms 197576 KB Output is correct
10 Correct 14 ms 197576 KB Output is correct
11 Correct 12 ms 197576 KB Output is correct
12 Correct 172 ms 197576 KB Output is correct
13 Correct 14 ms 197576 KB Output is correct
14 Correct 13 ms 197576 KB Output is correct
15 Runtime error 9556 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -