oj.uz

Submission #65010

# Submission time Handle Problem Language Result Execution time Memory
65010 2018-08-06T12:17:19 Z zetapi Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1008 ms 95012 KB 
#include <crocodile.h>
 
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define ll 	long long
#define itr ::iterator 
 
typedef pair<ll,ll>  pii;
 
const ll MAX=1e6;
const ll INF=1e14;
 
vector<pii> vec[MAX];
 
ll mark[MAX],dp[MAX],mn[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]));
	}
	for(int A=0;A<N;A++)
	{
		mn[A]=-1;
		dp[A]=-1;
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	for(int A=0;A<K;A++)
	{
		dp[P[A]]=0;
		mn[P[A]]=0;
		pq.push(mp(0,P[A]));
	}
	while(!pq.empty())
	{
		pii cur=pq.top();
		pq.pop();
		if(mark[cur.second])
			continue;
		mark[cur.second]=1;
		assert(cur.first==dp[cur.second]);
		for(auto A:vec[cur.second])
		{
			if(dp[A.first]==-1)
			{
				dp[A.first]=INF;
				mn[A.first]=cur.first+A.second;
			}
			else if(cur.first+A.second<dp[A.first])
			{
				dp[A.first]=cur.first+A.second;
				if(dp[A.first]<mn[A.first])			
					swap(dp[A.first],mn[A.first]);
				pq.push(mp(dp[A.first],A.first));
			}			
		}
	}
	assert(dp[0]<INF);
	return (int)dp[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 24040 KB Output is correct
3 Correct 25 ms 24040 KB Output is correct
4 Correct 26 ms 24140 KB Output is correct
5 Correct 28 ms 24140 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 22 ms 24188 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 24040 KB Output is correct
3 Correct 25 ms 24040 KB Output is correct
4 Correct 26 ms 24140 KB Output is correct
5 Correct 28 ms 24140 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 22 ms 24188 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct
9 Correct 29 ms 24396 KB Output is correct
10 Correct 25 ms 24396 KB Output is correct
11 Correct 26 ms 24396 KB Output is correct
12 Correct 29 ms 24608 KB Output is correct
13 Correct 31 ms 24736 KB Output is correct
14 Correct 23 ms 24736 KB Output is correct
15 Correct 23 ms 24736 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 24040 KB Output is correct
3 Correct 25 ms 24040 KB Output is correct
4 Correct 26 ms 24140 KB Output is correct
5 Correct 28 ms 24140 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 22 ms 24188 KB Output is correct
8 Correct 24 ms 24188 KB Output is correct
9 Correct 29 ms 24396 KB Output is correct
10 Correct 25 ms 24396 KB Output is correct
11 Correct 26 ms 24396 KB Output is correct
12 Correct 29 ms 24608 KB Output is correct
13 Correct 31 ms 24736 KB Output is correct
14 Correct 23 ms 24736 KB Output is correct
15 Correct 23 ms 24736 KB Output is correct
16 Correct 976 ms 88164 KB Output is correct
17 Correct 186 ms 88164 KB Output is correct
18 Correct 159 ms 88164 KB Output is correct
19 Correct 1008 ms 95012 KB Output is correct
20 Correct 508 ms 95012 KB Output is correct
21 Correct 101 ms 95012 KB Output is correct
22 Correct 519 ms 95012 KB Output is correct