oj.uz

Submission #4611

# Submission time Handle Problem Language Result Execution time Memory
4611 2013-11-10T09:14:03 Z cki86201 Wombats (IOI13_wombats) C++
76 / 100
 20000 ms 177772 KB 
#include "wombats.h"
#include<stdlib.h>
#include<queue>
#include<vector>
#include<functional>
#include<string.h>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> P;
typedef pair<int,P> Pi;
const int id = 512;
const int inf = 1e9;
const int bz = 10;

int H[5000][200],V[5000][200];
int T[1030][200][200];
int R,C;

void upd(int x,int y)
{
	int i,j;
	int A[200];
	memset(A,0,sizeof(A));
	for(i=x-1;i>=0;i--)A[i]=A[i+1]+H[bz*y][i];
	for(i=x+1;i<C;i++)A[i]=A[i-1]+H[bz*y][i-1];
	bool check[200];
	for(i=bz*y+1;i<=bz*y+bz && i<R;i++){
		priority_queue <P,vector<P>, greater<P> > pq;
		memset(check,0,sizeof(check));
		for(j=0;j<C;j++)pq.push(P(A[j]+V[i-1][j],j));
		int cnt = 0;
		while(!pq.empty() && cnt!=C){
			P t = pq.top();
			pq.pop();
			if(check[t.Y])continue;
			check[t.Y]=1;
			A[t.Y]=t.X;
			cnt++;
			if(t.Y+1<C && !check[t.Y+1])pq.push(P(t.X+H[i][t.Y],t.Y+1));
			if(t.Y!=0 && !check[t.Y-1])pq.push(P(t.X+H[i][t.Y-1],t.Y-1));
		}
	}
	for(i=0;i<C;i++)T[id+y][x][i]=A[i];
}

void Union(int t)
{
	int i,j,k;
	int sk[200];
	for(i=0;i<C;i++)sk[i]=0;
	for(i=0;i<C;i++)for(j=0;j<C;j++)T[t][i][j]=inf;
	for(i=C-1;i>=-C+1;i--){
		for(j=min(C-1,C-i-1);j>=0&&j+i>=0;j--){
			int s=j==max(0,-i)?0:sk[j-1];
			int d=j==min(C-1,C-i-1)?C-1:sk[j];
			for(k=s;k<=d;k++){
				if(T[t][j][j+i] > T[t<<1][j][k] + T[t<<1|1][k][j+i]){
					T[t][j][j+i]=T[t<<1][j][k] + T[t<<1|1][k][j+i];
					sk[j]=k;
				}
			}
		}
	}
	for(i=0;i<C;i++)if(T[t][i][i]==inf)T[t][i][i]=0;
}

void init(int R, int C, int H_[5000][200], int V_[5000][200]){
	int i,j;
	for(i=0;i<R;i++)for(j=0;j<C-1;j++)H[i][j]=H_[i][j];
	for(i=0;i<R-1;i++)for(j=0;j<C;j++)V[i][j]=V_[i][j];
	::R=R;
	::C=C;
	for(i=0;i<C;i++){
		for(j=0;bz*j<R;j++){
			upd(i,j);
		}
		for(;j<id;j++){
			for(int u=0;u<C;u++)T[id+j][i][u]=i==u?0:inf;
		}
	}
	for(i=id-1;i;i--)Union(i);
}

void changeH(int P, int Q, int W){
	H[P][Q]=W;
	int i,r=P/bz;
	for(i=0;i<C;i++)upd(i,r);
	if(P%bz == 0 && P){
		for(i=0;i<C;i++)upd(i,r-1);
		int t=(r+id-1)/2;
		while(t){Union(t);t>>=1;}
	}
	r+=id;
	r>>=1;
	while(r){
		Union(r);
		r>>=1;
	}
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    int i,r=P/bz;
	for(i=0;i<C;i++)upd(i,r);
	r+=id;
	r>>=1;
	while(r){
		Union(r);
		r>>=1;
	}
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 177772 KB Output is correct
2 Correct 0 ms 177772 KB Output is correct
3 Correct 88 ms 177772 KB Output is correct
4 Correct 4 ms 177772 KB Output is correct
5 Correct 4 ms 177772 KB Output is correct
6 Correct 0 ms 177772 KB Output is correct
7 Correct 0 ms 177772 KB Output is correct
8 Correct 0 ms 177772 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 177772 KB Output is correct
2 Correct 0 ms 177772 KB Output is correct
3 Correct 0 ms 177772 KB Output is correct
4 Correct 0 ms 177772 KB Output is correct
5 Correct 8 ms 177772 KB Output is correct
6 Correct 4 ms 177772 KB Output is correct
7 Correct 8 ms 177772 KB Output is correct
8 Correct 0 ms 177772 KB Output is correct
9 Correct 0 ms 177772 KB Output is correct
10 Correct 4 ms 177772 KB Output is correct
11 Correct 84 ms 177772 KB Output is correct
12 Correct 4 ms 177772 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2204 ms 177772 KB Output is correct
2 Correct 1016 ms 177772 KB Output is correct
3 Correct 2372 ms 177772 KB Output is correct
4 Correct 2240 ms 177772 KB Output is correct
5 Correct 2256 ms 177772 KB Output is correct
6 Correct 0 ms 177772 KB Output is correct
7 Correct 0 ms 177772 KB Output is correct
8 Correct 0 ms 177772 KB Output is correct
9 Correct 5620 ms 177772 KB Output is correct
10 Correct 0 ms 177772 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 177772 KB Output is correct
2 Correct 12 ms 177772 KB Output is correct
3 Correct 4 ms 177772 KB Output is correct
4 Correct 56 ms 177772 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2180 ms 177772 KB Output is correct
2 Correct 1004 ms 177772 KB Output is correct
3 Correct 2404 ms 177772 KB Output is correct
4 Correct 2244 ms 177772 KB Output is correct
5 Correct 2256 ms 177772 KB Output is correct
6 Correct 4 ms 177772 KB Output is correct
7 Correct 12 ms 177772 KB Output is correct
8 Correct 12 ms 177772 KB Output is correct
9 Correct 48 ms 177772 KB Output is correct
10 Correct 0 ms 177772 KB Output is correct
11 Correct 0 ms 177772 KB Output is correct
12 Correct 88 ms 177772 KB Output is correct
13 Correct 0 ms 177772 KB Output is correct
14 Correct 4 ms 177772 KB Output is correct
15 Correct 0 ms 177772 KB Output is correct
16 Correct 0 ms 177772 KB Output is correct
17 Correct 0 ms 177772 KB Output is correct
18 Correct 0 ms 177772 KB Output is correct
19 Correct 8 ms 177772 KB Output is correct
20 Correct 4 ms 177772 KB Output is correct
21 Correct 12 ms 177772 KB Output is correct
22 Correct 0 ms 177772 KB Output is correct
23 Correct 8 ms 177772 KB Output is correct
24 Correct 4 ms 177772 KB Output is correct
25 Correct 92 ms 177772 KB Output is correct
26 Correct 4 ms 177772 KB Output is correct
27 Correct 5436 ms 177772 KB Output is correct
28 Correct 10012 ms 177772 KB Output is correct
29 Correct 18601 ms 177772 KB Output is correct
30 Correct 17585 ms 177772 KB Output is correct
31 Correct 11464 ms 177772 KB Output is correct
32 Correct 0 ms 177772 KB Output is correct

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2180 ms 177772 KB Output is correct
2 Correct 1032 ms 177772 KB Output is correct
3 Correct 2368 ms 177772 KB Output is correct
4 Correct 2244 ms 177772 KB Output is correct
5 Correct 2284 ms 177772 KB Output is correct
6 Correct 4 ms 177772 KB Output is correct
7 Correct 8 ms 177772 KB Output is correct
8 Correct 8 ms 177772 KB Output is correct
9 Correct 52 ms 177772 KB Output is correct
10 Correct 0 ms 177772 KB Output is correct
11 Correct 0 ms 177772 KB Output is correct
12 Correct 80 ms 177772 KB Output is correct
13 Correct 0 ms 177772 KB Output is correct
14 Correct 0 ms 177772 KB Output is correct
15 Execution timed out 20000 ms 177768 KB Program timed out
16 Halted 0 ms 0 KB -