Submission #64836

#	Time	Username	Problem	Language	Result	Execution time	Memory
64836		zetapi	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1626 ms	59148 KiB

crocodile

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

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         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));
                 ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11