oj.uz

Submission #15665

# Submission time Handle Problem Language Result Execution time Memory
15665 2015-07-14T06:56:03 Z progressive Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 173828 KB 
#include "wombats.h"
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
static const int bucket=3; 
static const int MAXN=1<<11;
static const int MAXC=100;
static int idx[2*MAXN][MAXC][MAXC]; //78.125MB
static int R;
static int C;
static int H[MAXN*bucket][MAXC];//3.90625MB
static int V[MAXN*bucket][MAXC];//3.90625MB
static void dijkFunction(int a)
{
	int saveidx=a+MAXN;
	int bias=a*bucket;
	int dijk[bucket+1][MAXC];
	if(bias>=R)
	{
		idx[saveidx][0][0]=-1;
		return;
	}	
	for(int i=0;i<C;i++)
	{
		memset(dijk,-1,sizeof(dijk) );
		priority_queue<pair<int,pair<int,int> > > PQ;
		PQ.push(make_pair(-0,make_pair(0,i)));
		while(!PQ.empty())
		{
			int dist=-PQ.top().first;
			int xcord=PQ.top().second.first;
			int ycord=PQ.top().second.second;
			PQ.pop();
			if(dijk[xcord][ycord]!=-1) continue;
			dijk[xcord][ycord]=dist;
			if(xcord==bucket) continue;
			if(xcord==R-bias) continue;
			if(xcord!=R-bias-1) PQ.push(make_pair(-(dist+V[xcord+bias][ycord]),make_pair(xcord+1,ycord)));
			if(ycord!=0)
				PQ.push(make_pair(-(dist+H[xcord+bias][ycord-1]),make_pair(xcord,ycord-1)));
			if(ycord!=C-1)
				PQ.push(make_pair(-(dist+H[xcord+bias][ycord]),make_pair(xcord,ycord+1)));
		}
		for(int j=0;j<C;j++)
			idx[saveidx][i][j]=dijk[min(R-1-bias,bucket)][j];
	}
}
static void updateidx(int ind)
{
	int ind1=ind*2, ind2=ind*2+1;
	if(idx[ind2][0][0]<0)
	{
		for(int i=0;i<C;i++)
			for(int j=0;j<C;j++)
				idx[ind][i][j]=idx[ind1][i][j];
		return;
	}
	int usedK[MAXC+2][MAXC+2];
	for(int i=0;i<C+2;i++) usedK[i][0]=0;
	for(int i=0;i<C+2;i++) usedK[0][i]=0;
	for(int i=0;i<C+2;i++) usedK[C+1][i]=C-1;
	for(int i=0;i<C+2;i++) usedK[i][C+1]=C-1;
	//printf("%d\n",ind);
	for(int imj=C-1;imj>=1-C;imj--)
	{
		for(int i=max(imj,0);i<=min(C-1+imj,C-1);i++)
		{
			int j=i-imj;
		//	fprintf(stderr,"%d %d %d~%d\n",i,j,usedK[i+1][j],usedK[i+2][j+1]);
			idx[ind][i][j]=0x3f3f3f3f;
			int minK=-1;
			for(int K=usedK[i+1][j];K<=usedK[i+2][j+1];K++)
			{
				int val=idx[ind1][i][K]+idx[ind2][K][j];
				if(idx[ind][i][j]>val)
				{
					idx[ind][i][j]=val;
					minK=K;
				}
			}
			usedK[i+1][j+1]=minK;
		}	
	}
	/*
	//red herring
	for(int i=0;i<C;i++)
		for(int j=0;j<C;j++)
		{
			idx[ind][i][j]=0x3f3f3f3f;
			for(int k=0;k<C;k++)
				idx[ind][i][j]=min(idx[ind][i][j],idx[ind1][i][k]+idx[ind2][k][j]);
		}
	//*/
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
	::R=R;
	::C=C;
	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];
	for(int i=0;i<MAXN;i++) dijkFunction(i);
	for(int i=MAXN-1;i>0;i--)
		updateidx(i);
}
static void refresh(int a)
{

	dijkFunction(a);
	a+=MAXN;
	while(a!=1)
	{
		a/=2;
		updateidx(a);
	}
	return;
}
void changeH(int P, int Q, int W)
{
	int rbucket=P/bucket;
	H[P][Q]=W;
	refresh(rbucket);
}

void changeV(int P, int Q, int W)
{
	int rbucket=P/bucket;
	V[P][Q]=W;
	refresh(rbucket);
}

int escape(int V1, int V2)
{
	return idx[1][V1][V2];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 173828 KB Output is correct - 505 tokens
2 Correct 10 ms 173828 KB Output is correct - 505 tokens
3 Correct 86 ms 173828 KB Output is correct - 200005 tokens
4 Correct 4 ms 173828 KB Output is correct - 505 tokens
5 Correct 6 ms 173828 KB Output is correct - 505 tokens
6 Correct 0 ms 173828 KB Output is correct - 6 tokens
7 Correct 0 ms 173828 KB Output is correct - 6 tokens
8 Correct 0 ms 173828 KB Output is correct - 6 tokens

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 173828 KB Output is correct - 6 tokens
2 Correct 0 ms 173828 KB Output is correct - 6 tokens
3 Correct 0 ms 173828 KB Output is correct - 6 tokens
4 Correct 13 ms 173828 KB Output is correct - 405 tokens
5 Correct 4 ms 173828 KB Output is correct - 405 tokens
6 Correct 0 ms 173828 KB Output is correct - 405 tokens
7 Correct 8 ms 173828 KB Output is correct - 405 tokens
8 Correct 3 ms 173828 KB Output is correct - 366 tokens
9 Correct 9 ms 173828 KB Output is correct - 405 tokens
10 Correct 3 ms 173828 KB Output is correct - 366 tokens
11 Correct 59 ms 173828 KB Output is correct - 200005 tokens
12 Correct 0 ms 173828 KB Output is correct - 405 tokens

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 173828 KB Output is correct - 105 tokens
2 Correct 1606 ms 173828 KB Output is correct - 105 tokens
3 Correct 1000 ms 173828 KB Output is correct - 105 tokens
4 Correct 1017 ms 173828 KB Output is correct - 105 tokens
5 Correct 983 ms 173828 KB Output is correct - 105 tokens
6 Correct 0 ms 173828 KB Output is correct - 6 tokens
7 Correct 3 ms 173828 KB Output is correct - 6 tokens
8 Correct 0 ms 173828 KB Output is correct - 6 tokens
9 Correct 5934 ms 173828 KB Output is correct - 105 tokens
10 Correct 0 ms 173828 KB Output is correct - 8 tokens

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 173828 KB Output is correct - 1005 tokens
2 Correct 5 ms 173828 KB Output is correct - 1005 tokens
3 Correct 7 ms 173828 KB Output is correct - 1005 tokens
4 Correct 45 ms 173828 KB Output is correct - 100005 tokens

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 173828 KB Output is correct - 105 tokens
2 Correct 1603 ms 173828 KB Output is correct - 105 tokens
3 Correct 1015 ms 173828 KB Output is correct - 105 tokens
4 Correct 1016 ms 173828 KB Output is correct - 105 tokens
5 Correct 990 ms 173828 KB Output is correct - 105 tokens
6 Correct 3 ms 173828 KB Output is correct - 1005 tokens
7 Correct 3 ms 173828 KB Output is correct - 1005 tokens
8 Correct 4 ms 173828 KB Output is correct - 1005 tokens
9 Correct 45 ms 173828 KB Output is correct - 100005 tokens
10 Correct 3 ms 173828 KB Output is correct - 505 tokens
11 Correct 0 ms 173828 KB Output is correct - 505 tokens
12 Correct 49 ms 173828 KB Output is correct - 200005 tokens
13 Correct 0 ms 173828 KB Output is correct - 505 tokens
14 Correct 4 ms 173828 KB Output is correct - 505 tokens
15 Correct 0 ms 173828 KB Output is correct - 6 tokens
16 Correct 0 ms 173828 KB Output is correct - 6 tokens
17 Correct 0 ms 173828 KB Output is correct - 6 tokens
18 Correct 0 ms 173828 KB Output is correct - 405 tokens
19 Correct 4 ms 173828 KB Output is correct - 405 tokens
20 Correct 3 ms 173828 KB Output is correct - 405 tokens
21 Correct 8 ms 173828 KB Output is correct - 405 tokens
22 Correct 8 ms 173828 KB Output is correct - 366 tokens
23 Correct 4 ms 173828 KB Output is correct - 405 tokens
24 Correct 4 ms 173828 KB Output is correct - 366 tokens
25 Correct 68 ms 173828 KB Output is correct - 200005 tokens
26 Correct 0 ms 173828 KB Output is correct - 405 tokens
27 Correct 5952 ms 173828 KB Output is correct - 105 tokens
28 Execution timed out 20000 ms 173828 KB Program timed out
29 Halted 0 ms 0 KB -

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 173828 KB Output is correct - 105 tokens
2 Correct 1586 ms 173828 KB Output is correct - 105 tokens
3 Correct 1003 ms 173828 KB Output is correct - 105 tokens
4 Correct 1017 ms 173828 KB Output is correct - 105 tokens
5 Correct 989 ms 173828 KB Output is correct - 105 tokens
6 Correct 0 ms 173828 KB Output is correct - 1005 tokens
7 Correct 4 ms 173828 KB Output is correct - 1005 tokens
8 Correct 4 ms 173828 KB Output is correct - 1005 tokens
9 Correct 47 ms 173828 KB Output is correct - 100005 tokens
10 Correct 8 ms 173828 KB Output is correct - 505 tokens
11 Correct 0 ms 173828 KB Output is correct - 505 tokens
12 Correct 75 ms 173828 KB Output is correct - 200005 tokens
13 Correct 5 ms 173828 KB Output is correct - 505 tokens
14 Correct 4 ms 173828 KB Output is correct - 505 tokens
15 Runtime error 17254 ms 173824 KB SIGSEGV Segmentation fault
16 Halted 0 ms 0 KB -