Submission #65006

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

crocodile

#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=1e6;
const int INF=1e9+9;
 
vector<pii> vec[MAX];
 
ll mark[MAX],dp[MAX],deg[MAX];
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{	
	for(int A=0;A<M;A++)
	{
		vec[R[A][0]].pb(mp(R[A][1],L[A]));
		vec[R[A][1]].pb(mp(R[A][0],L[A]));
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int A=0;A<K;A++)
	{
		deg[P[A]]=1;
		pq.push(mp(0,P[A]));
	}
	while(!pq.empty())
	{
		pii cur=pq.top();
		pq.pop();
		deg[cur.second]++;
		if(deg[cur.second]!=2)
			continue;
		dp[cur.second]=cur.first;
		for(auto A:vec[cur.second])
			if(deg[A.first]<2)
				pq.push(mp(cur.first+A.second,A.first));
	}
	return dp[0];
}

/*signed main()
{
	int N,M,K,R[MAX][2],L[MAX],P[MAX];
	cin>>N>>M>>K;
	for(int A=0;A<M;A++)
		cin>>R[A][0]>>R[A][1]>>L[A];
	for(int A=0;A<K;A++)
		cin>>P[A];
	cout<<travel_plan(N,M,R,L,K,P);
	return 0;
}*/

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