Submission #198769

#	Time	Username	Problem	Language	Result	Execution time	Memory
198769		arnold518	Wombats (IOI13_wombats)	C++14	100 / 100	9960 ms	196996 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXR = 5000;
const int MAXC = 200;
const int INF = 987654321;

int R, C, H[MAXR+10][MAXC+10], V[MAXR+10][MAXC+10];

struct Node
{
	vector<vector<int>> V;
	Node() { V=vector<vector<int>>(C, vector<int>(C)); }
};
Node tree[MAXR*4+10];
int opt[MAXC+10][MAXC+10];

void add(Node &now, Node &lc, Node &rc, int pos)
{
	int i, j, k, p;
	now=Node();

	for(k=-(C-1); k<=(C-1); k++)
	{
		for(i=max(0, k); i<min(C+k, C); i++)
		{
			j=i-k; int l, r;

			if(i==0) l=0;
			else l=opt[i-1][j];

			if(j==C-1) r=C-1;
			else r=opt[i][j+1];

			int t=l; now.V[i][j]=INF;
			for(p=l; p<=r; p++)
			{
				if(now.V[i][j]>lc.V[i][p]+rc.V[p][j]+V[pos][p])
				{
					t=p; now.V[i][j]=lc.V[i][p]+rc.V[p][j]+V[pos][p];
				}
			}
			opt[i][j]=t;
		}
	}
}

void initnode(Node &now, int tl, int tr)
{
	int i, j, k;

	now=Node();
	for(i=0; i<C; i++)
	{
		int s=0;
		for(j=i+1; j<C; j++)
		{
			s+=H[tl][j-1];
			now.V[i][j]=now.V[j][i]=s;
		}
	}

	for(k=tl+1; k<=tr; k++)
	{
		Node p;
		for(i=0; i<C; i++)
		{
			int s=0;
			for(j=i+1; j<C; j++)
			{
				s+=H[k][j-1];
				p.V[i][j]=p.V[j][i]=s;
			}
		}
		Node t;
		add(t, now, p, k-1);
		now=t;
	}
}

void init(int node, int tl, int tr)
{
	if(tr-tl+1<=10)
	{
		initnode(tree[node], tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	add(tree[node], tree[node*2], tree[node*2+1], mid);
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
	int i, j;
	R=_R; C=_C;
	for(i=0; i<R; i++) for(j=0; j+1<C; j++) H[i][j]=_H[i][j];
	for(i=0; i+1<R; i++) for(j=0; j<C; j++) V[i][j]=_V[i][j];

	init(1, 0, R-1);
}

void updateH(int node, int tl, int tr, int y)
{
	if(tr-tl+1<=10)
	{
		initnode(tree[node], tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	if(y<=mid) updateH(node*2, tl, mid, y);
	else updateH(node*2+1, mid+1, tr, y);
	add(tree[node], tree[node*2], tree[node*2+1], mid);
}

void updateV(int node, int tl, int tr, int y)
{
	if(tr-tl+1<=10)
	{
		initnode(tree[node], tl, tr);
		return;
	}
	int mid=tl+tr>>1;
	if(y==mid) { add(tree[node], tree[node*2], tree[node*2+1], mid); return; }
	if(y<=mid) updateV(node*2, tl, mid, y);
	else updateV(node*2+1, mid+1, tr, y);
	add(tree[node], tree[node*2], tree[node*2+1], mid);
}

void changeH(int P, int Q, int W)
{
	H[P][Q]=W;
	updateH(1, 0, R-1, P);
}

void changeV(int P, int Q, int W)
{
	V[P][Q]=W;
	updateV(1, 0, R-1, P);
}

int escape(int V1, int V2)
{
	return tree[1].V[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;
      ^~~
wombats.cpp: In function 'void init(int, int, int)':
wombats.cpp:93:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wombats.cpp: In function 'void updateH(int, int, int, int)':
wombats.cpp:116:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wombats.cpp: In function 'void updateV(int, int, int, int)':
wombats.cpp:129:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24