oj.uz

Submission #4590

# Submission time Handle Problem Language Result Execution time Memory
4590 2013-11-07T09:59:55 Z cki86201 Wombats (IOI13_wombats) C++
37 / 100
 12288 ms 18100 KB 
#include "wombats.h"
#include<stdlib.h>
#include<queue>
#include<vector>
#include<functional>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> P;
typedef pair<int,P> Pi;

int H[5000][200],V[5000][200];
int T[5000],T2[2][5000][2];
int R,C;
bool check[5000][200];

//55point;

void build2()
{
	int i;
	T2[0][0][0]=0,T2[0][0][1]=H[0][0];
	for(i=1;i<R;i++){
		if(T2[0][i-1][0]>T2[0][i-1][1]){
			T2[0][i][1]=T2[0][i-1][1]+V[i-1][1];
			T2[0][i][0]=min(T2[0][i][1]+H[i][0],T2[0][i-1][0]+V[i-1][0]);
		}
		else{
			T2[0][i][0]=T2[0][i-1][0]+V[i-1][0];
			T2[0][i][1]=min(T2[0][i][0]+H[i][0],T2[0][i-1][1]+V[i-1][1]);
		}
	}
	T2[1][0][1]=0,T2[1][0][0]=H[0][0];
	for(i=1;i<R;i++){
		if(T2[1][i-1][0]>T2[1][i-1][1]){
			T2[1][i][1]=T2[1][i-1][1]+V[i-1][1];
			T2[1][i][0]=min(T2[1][i][1]+H[i][0],T2[1][i-1][0]+V[i-1][0]);
		}
		else{
			T2[1][i][0]=T2[1][i-1][0]+V[i-1][0];
			T2[1][i][1]=min(T2[1][i][0]+H[i][0],T2[1][i-1][1]+V[i-1][1]);
		}
	}
}

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;
	if(C==1)for(i=1;i<R;i++)T[i]=T[i-1]+V[i-1][0];
	if(C==2)build2();
}

void changeH(int P, int Q, int W){
	H[P][Q]=W;
	if(C==2)build2();
}

void changeV(int P, int Q, int W) {
    V[P][Q]=W;
    if(C==1)for(int i=P+1;i<R;i++)T[i]=T[i-1]+V[i-1][0];
    if(C==2)build2();
}

int escape(int V1, int V2) {
	if(C==1)return T[R-1];
	if(C==2)return T2[V1][R-1][V2];
	priority_queue <Pi,vector<Pi>,greater<Pi> > pq;
	int i,j;
	for(i=0;i<R;i++)for(j=0;j<C;j++)check[i][j]=0;
	pq.push(Pi(0,P(0,V1)));
	while(!pq.empty()){
		Pi t=pq.top();
		pq.pop();
		if(check[t.Y.X][t.Y.Y])continue;
		check[t.Y.X][t.Y.Y]=1;
		if(t.Y.X == R-1 && t.Y.Y == V2)return t.X;
		if(t.Y.Y!=C-1 && !check[t.Y.X][t.Y.Y+1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y],P(t.Y.X,t.Y.Y+1)));
		if(t.Y.Y && !check[t.Y.X][t.Y.Y-1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y-1],P(t.Y.X,t.Y.Y-1)));
		if(t.Y.X!=R-1 && !check[t.Y.X+1][t.Y.Y])pq.push(Pi(t.X+V[t.Y.X][t.Y.Y],P(t.Y.X+1,t.Y.Y)));
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17908 KB Output is correct
2 Correct 0 ms 17908 KB Output is correct
3 Correct 96 ms 17908 KB Output is correct
4 Correct 4 ms 17908 KB Output is correct
5 Correct 12 ms 17908 KB Output is correct
6 Correct 0 ms 17908 KB Output is correct
7 Correct 0 ms 17908 KB Output is correct
8 Correct 0 ms 17908 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17908 KB Output is correct
2 Correct 0 ms 17908 KB Output is correct
3 Correct 0 ms 17908 KB Output is correct
4 Correct 28 ms 17908 KB Output is correct
5 Correct 20 ms 17908 KB Output is correct
6 Correct 24 ms 17908 KB Output is correct
7 Correct 16 ms 17908 KB Output is correct
8 Correct 20 ms 17908 KB Output is correct
9 Correct 24 ms 17908 KB Output is correct
10 Correct 20 ms 17908 KB Output is correct
11 Correct 12288 ms 17908 KB Output is correct
12 Correct 24 ms 17908 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 17908 KB Output is correct
2 Correct 168 ms 18100 KB Output is correct
3 Correct 212 ms 17908 KB Output is correct
4 Correct 208 ms 17908 KB Output is correct
5 Correct 204 ms 17908 KB Output is correct
6 Correct 0 ms 17908 KB Output is correct
7 Correct 0 ms 17908 KB Output is correct
8 Correct 0 ms 17908 KB Output is correct
9 Correct 252 ms 17908 KB Output is correct
10 Correct 0 ms 17908 KB Output is correct

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 17908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 17908 KB Output is correct
2 Correct 164 ms 18100 KB Output is correct
3 Correct 208 ms 17908 KB Output is correct
4 Correct 208 ms 17908 KB Output is correct
5 Correct 212 ms 17908 KB Output is correct
6 Incorrect 68 ms 17908 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 17908 KB Output is correct
2 Correct 164 ms 18100 KB Output is correct
3 Correct 212 ms 17908 KB Output is correct
4 Correct 212 ms 17908 KB Output is correct
5 Correct 212 ms 17908 KB Output is correct
6 Incorrect 60 ms 17908 KB Output isn't correct
7 Halted 0 ms 0 KB -