oj.uz

Submission #6995

# Submission time Handle Problem Language Result Execution time Memory
6995 2014-07-12T08:04:56 Z gs13068 Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 1252 ms 173292 KB 
#include<vector>
#include<queue>

std::vector<std::pair<int,int> > G[100000];
std::priority_queue<std::pair<int,int> > PQ;
std::pair<int,int> P;
int D[100000];

int travel_plan(int N,int M,int R[][2],int L[],int K,int X[])
{
    int i;
    for(i=0;i<N;i++)
	{
		G[i].clear();
		D[i]=-1;
	}
    for(i=0;i<M;i++)
	{
		G[R[i][0]].push_back(std::make_pair(R[i][1],L[i]));
		G[R[i][1]].push_back(std::make_pair(R[i][0],L[i]));
	}
	for(i=0;i<K;i++)
	{
        D[X[i]]=-2;
		PQ.push(std::make_pair(0,X[i]));
	}
    while(!PQ.empty())
	{
		P=PQ.top();
		PQ.pop();
		if(D[P.second]>=0)continue;
		if(D[P.second]==-1)
		{
			D[P.second]=-2;
			continue;
		}
		D[P.second]=-P.first;
        for(i=0;i<G[P.second].size();i++)PQ.push(std::make_pair(P.first-G[P.second][i].second,G[P.second][i].first));
	}
	return D[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1108 ms 170908 KB Output is correct
2 Correct 100 ms 125948 KB Output is correct
3 Correct 144 ms 127136 KB Output is correct
4 Correct 1252 ms 173292 KB Output is correct
5 Correct 768 ms 168752 KB Output is correct
6 Correct 56 ms 123572 KB Output is correct
7 Correct 696 ms 140384 KB Output is correct