oj.uz

Submission #4588

# Submission time Handle Problem Language Result Execution time Memory
4588 2013-11-07T09:37:16 Z cki86201 Wombats (IOI13_wombats) C++
28 / 100
 20000 ms 18004 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 R,C;
bool check[5000][200];

//37point;

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;
}

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

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

int escape(int V1, int 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(!check[t.Y.X][t.Y.Y+1] && t.Y.Y!=C-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(!check[t.Y.X+1][t.Y.Y] && t.Y.X!=R-1)pq.push(Pi(t.X+V[t.Y.X][t.Y.Y],P(t.Y.X+1,t.Y.Y)));
	}
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 17812 KB Output is correct
2 Correct 124 ms 17812 KB Output is correct
3 Execution timed out 20000 ms 17812 KB Program timed out
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 17812 KB Output is correct
2 Correct 160 ms 18004 KB Output is correct
3 Correct 212 ms 17812 KB Output is correct
4 Correct 208 ms 17812 KB Output is correct
5 Correct 208 ms 17812 KB Output is correct
6 Correct 0 ms 17812 KB Output is correct
7 Correct 0 ms 17812 KB Output is correct
8 Correct 0 ms 17812 KB Output is correct
9 Correct 248 ms 17812 KB Output is correct
10 Correct 0 ms 17812 KB Output is correct

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 17812 KB Output is correct
2 Correct 1612 ms 17812 KB Output is correct
3 Correct 844 ms 17812 KB Output is correct
4 Execution timed out 20000 ms 17812 KB Program timed out

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 17812 KB Output is correct
2 Correct 160 ms 18004 KB Output is correct
3 Correct 212 ms 17812 KB Output is correct
4 Correct 204 ms 17812 KB Output is correct
5 Correct 208 ms 17812 KB Output is correct
6 Correct 848 ms 17812 KB Output is correct
7 Correct 1616 ms 17812 KB Output is correct
8 Correct 840 ms 17812 KB Output is correct
9 Execution timed out 20000 ms 17812 KB Program timed out
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 17812 KB Output is correct
2 Correct 160 ms 18004 KB Output is correct
3 Correct 212 ms 17812 KB Output is correct
4 Correct 204 ms 17812 KB Output is correct
5 Correct 204 ms 17812 KB Output is correct
6 Correct 848 ms 17812 KB Output is correct
7 Correct 1616 ms 17812 KB Output is correct
8 Correct 840 ms 17812 KB Output is correct
9 Execution timed out 20000 ms 17812 KB Program timed out
10 Halted 0 ms 0 KB -