Submission #195811

#	Time	Username	Problem	Language	Result	Execution time	Memory
195811		rkm0959	Wombats (IOI13_wombats)	C++14	Compilation error	0 ms	0 KiB

wombats

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long double ldb;
typedef long long int ll;
typedef unsigned long long int ull;
typedef complex<double> base;
ll mod=1e9+7;

struct node
{
	int Ldx, Rdx, S, E; // L, R index, [S, E]
	int a[202][202]; // u -> v minimum value
};

vector<node> nodes;
int R, C, Q;
int H[5020][202]; // H[i][j] : (i, j) -> (i, j+1)
int V[5020][202]; // V[i][j] : (i, j) -> (i+1, j)

void calc(int idx, int s, int e) // naive calc
{
	int dp_1[202][202]={0}, dp_2[202][202]={0};
	int CV[202][202]={0}, OPT[202][202]={0}, PS[202]={0}, i, j, k, u, v;
	for(i=1 ; i<=C ; i++)
	{
		for(j=1 ; j<=C ; j++)
		{
			if(i==j) dp_1[i][j]=0;
			else dp_1[i][j]=1e9+7;
		}
	}
	for(i=s ; i<=e ; i++)
	{
		for(j=1 ; j<=C-1 ; j++) PS[j]=PS[j-1]+H[i][j];
		for(j=1 ; j<=C ; j++)
		{
			for(k=1 ; k<=C ; k++)
			{
				OPT[j][k]=0;
				if(j==k) CV[j][k]=0+V[i][k];
				if(j<k) CV[j][k]=PS[k-1]-PS[j-1]+V[i][k];
				if(j>k) CV[j][k]=PS[j-1]-PS[k-1]+V[i][k];
			}
		}
		for(k=1-C ; k<=C ; k++)
		{
			for(u=1 ; u<=C ; u++)
			{
				v=u+k; if(v<1 || v>C) continue;
				dp_2[u][v]=1e9+7;
				int l=OPT[u][v-1]?OPT[u][v-1]:1;
				int r=OPT[u+1][v]?OPT[u+1][v]:C;
				for(j=l ; j<=r ; j++) 
					if(dp_2[u][v]>dp_1[u][j]+CV[j][v])
						OPT[u][v]=j, dp_2[u][v]=dp_1[u][j]+CV[j][v];
			}
		}
		for(j=1 ; j<=C ; j++)
			for(k=1 ; k<=C ; k++)
				dp_1[j][k]=dp_2[j][k];
	}
	for(i=1 ; i<=C ; i++)
		for(j=1 ; j<=C ; j++)
			nodes[idx].a[i][j]=dp_1[i][j];
	return;
}

void merger(int idx, int Ldx, int Rdx, int s, int e)
{
	int OPT[202][202]={0}, dp[202][202], i, j, k, v;
	for(k=1-C ; k<=C ; k++)
	{
		for(i=1 ; i<=C ; i++)
		{
			j=i+k; dp[i][j]=1e9+7;
			int l=OPT[i][j-1]?OPT[i][j-1]:1;
			int r=OPT[i+1][j]?OPT[i+1][j]:C;
			for(v=l ; v<=r ; v++)
				if(dp[i][j]>nodes[Ldx].a[i][v]+nodes[Rdx].a[v][j])
					OPT[i][j]=v, dp[i][j]=nodes[Ldx].a[i][v]+nodes[Rdx].a[v][j];
		}
	}
	for(i=1 ; i<=C ; i++)
		for(j=1 ; j<=C ; j++)
			nodes[idx].a[i][j]=dp[i][j];
}

void build(int idx, int s, int e)
{
	node X; X.Ldx=-1; X.Rdx=-1; X.S=s; X.E=e;
	nodes.push_back(X);
	if(e-s<20) { calc(nodes.size()-1, s, e); return; }
	int m=(s+e)>>1;
	if(nodes[idx].Ldx==-1)
	{
		nodes[idx].Ldx=nodes.size(); 
		build(nodes.size(), s, m);
	}
	if(X.Rdx==-1)
	{
		nodes[idx].Rdx=nodes.size();
		build(nodes.size(), m+1, e);
	}
	merger(idx, nodes[idx].Ldx, nodes[idx].Rdx, s, e);
}

void update(int idx, int s, int e, int l, int r)
{
	if(l>e || r<s) return;
	if(e-s<20) { calc(idx, s, e); return; }
	int m=(s+e)>>1;
	if(nodes[idx].Ldx!=-1) update(nodes[idx].Ldx, s, m, l, r);
	if(nodes[idx].Rdx!=-1) update(nodes[idx].Rdx, m+1, e, l, r);
	merger(idx, nodes[idx].Ldx, nodes[idx].Rdx, s, e);
}

int main(void)
{
	fio; int i, j, whi, u, v, w; cin>>R>>C;
	for(i=1 ; i<=R ; i++)
		for(j=1 ; j<=C-1 ; j++) cin>>H[i][j];
	for(i=1 ; i<=R-1 ; i++)
		for(j=1 ; j<=C ; j++) cin>>V[i][j];
	build(0, 1, R); cin>>Q;
	while(Q--)
	{
		cin>>whi;
		if(whi==1) { cin>>u>>v>>w; H[u+1][v+1]=w; update(0, 1, R, u+1, u+1); }
		if(whi==2) { cin>>u>>v>>w; V[u+1][v+1]=w; update(0, 1, R, u+1, u+2); }
		if(whi==3) { cin>>u>>v; cout<<nodes[0].a[u+1][v+1]<<"\n"; }
	}
	return 0;
}

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;
      ^~~
/tmp/ccOafeni.o: In function `main':
wombats.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccrorC2g.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccrorC2g.o: In function `main':
grader.c:(.text.startup+0x103): undefined reference to `init'
grader.c:(.text.startup+0x164): undefined reference to `escape'
grader.c:(.text.startup+0x1cf): undefined reference to `changeH'
grader.c:(.text.startup+0x23b): undefined reference to `changeV'
collect2: error: ld returned 1 exit status