oj.uz

Submission #5039

# Submission time Handle Problem Language Result Execution time Memory
5039 2014-01-29T06:32:18 Z cki86201 Crocodile's Underground City (IOI11_crocodile) C++
46 / 100
 640 ms 146280 KB 
#include "crocodile.h"
#include <queue>
using namespace std;

typedef pair<int,int> Pi;
#define X first
#define Y second

int st[100010], en[2000020], nxt[2000020], len[2000020];
void add(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,len[c]=l,en[c]=e;}

priority_queue <Pi, vector<Pi>, greater<Pi> > pq;
int p[100010][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	int i;
	for(i=0;i<N;i++)st[i] = -1;
	for(i=0;i<M;i++)add(R[i][0],R[i][1],L[i],i<<1), add(R[i][1],R[i][0],L[i],i<<1|1);
	for(i=0;i<K;i++)pq.push(Pi(0,P[i]));
	while(!pq.empty()){
		Pi tmp = pq.top();
		pq.pop();
		if(tmp.X > p[tmp.Y][1])continue;
		for(i=st[tmp.Y];i!=-1;i=nxt[i]){
			int &a = p[en[i]][0], &b = p[en[i]][1], l = tmp.X + len[i];
			if(!a||a>l){
				b=a, a=l;
				if(b)pq.push(Pi(b, en[i]));
			}
			else if(!b||b>l)b=l, pq.push(Pi(b, en[i]));
		}
	}
	return p[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 143204 KB Output is correct
2 Correct 0 ms 143204 KB Output is correct
3 Correct 0 ms 143204 KB Output is correct
4 Correct 4 ms 143204 KB Output is correct
5 Correct 0 ms 143204 KB Output is correct
6 Incorrect 0 ms 143204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

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