oj.uz

Submission #5040

# Submission time Handle Problem Language Result Execution time Memory
5040 2014-01-29T06:40:46 Z cki86201 Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 652 ms 146376 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];
bool chk[100010];

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(chk[tmp.Y])continue;
		chk[tmp.Y] = 1;
		for(i=st[tmp.Y];i!=-1;i=nxt[i]){
			if(chk[en[i]])continue;
			int &a = p[en[i]][0], &b = p[en[i]][1], l = tmp.X + len[i], s = b;
			if(!a||a>l)b=a, a=l;
			else if(!b||b>l)b=l;
			if(b!=s)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 143300 KB Output is correct
2 Correct 0 ms 143300 KB Output is correct
3 Correct 0 ms 143300 KB Output is correct
4 Correct 0 ms 143300 KB Output is correct
5 Correct 0 ms 143300 KB Output is correct
6 Correct 0 ms 143300 KB Output is correct
7 Correct 0 ms 143300 KB Output is correct
8 Correct 0 ms 143300 KB Output is correct

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 144840 KB Output is correct
2 Correct 72 ms 143300 KB Output is correct
3 Correct 80 ms 143300 KB Output is correct
4 Correct 652 ms 146376 KB Output is correct
5 Correct 384 ms 143300 KB Output is correct
6 Correct 32 ms 143300 KB Output is correct
7 Correct 356 ms 143300 KB Output is correct