oj.uz

Submission #4589

# Submission time Handle Problem Language Result Execution time Memory
4589 2013-11-07T09:41:39 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(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
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 24 ms 17812 KB Output is correct
5 Correct 20 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 12076 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 204 ms 17812 KB Output is correct
2 Correct 164 ms 18004 KB Output is correct
3 Correct 208 ms 17812 KB Output is correct
4 Correct 212 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 868 ms 17812 KB Output is correct
2 Correct 1656 ms 17812 KB Output is correct
3 Correct 868 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 212 ms 17812 KB Output is correct
5 Correct 220 ms 17812 KB Output is correct
6 Correct 868 ms 17812 KB Output is correct
7 Correct 1632 ms 17812 KB Output is correct
8 Correct 868 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 168 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 876 ms 17812 KB Output is correct
7 Correct 1652 ms 17812 KB Output is correct
8 Correct 896 ms 17812 KB Output is correct
9 Execution timed out 20000 ms 17812 KB Program timed out
10 Halted 0 ms 0 KB -