oj.uz

Submission #438048

# Submission time Handle Problem Language Result Execution time Memory
438048 2021-06-27T13:23:55 Z adamjinwei Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 814 ms 69676 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define inf 1000000007
#define mod 1000000007
#define rnd() rand_num()
#define bigrnd() dis(rand_num)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
using namespace std;
unsigned sed=std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rand_num(sed);
uniform_int_distribution<long long> dis(0,inf);
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n;
int h[100005],e[2000005],w[2000005],ne[2000005],idx;
int dist[100005][2];
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
signed travel_plan(signed N,signed M,signed R[][2],signed L[],signed K,signed P[])
{
	n=N;
	memset(h,-1,sizeof(h));
	for(int i=0;i<M;++i)
	{
		add(R[i][0],R[i][1],L[i]);
		add(R[i][1],R[i][0],L[i]);
	}
	memset(dist,0x3f,sizeof(dist));
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	for(int i=0;i<K;++i)
	{
		dist[P[i]][0]=dist[P[i]][1]=0;
		pq.push(make_pair(0,P[i]));
	}
	while(!pq.empty())
	{
		pair<int,int> p=pq.top();
		pq.pop();
		if(dist[p.second][1]!=p.first) continue;
		for(int i=h[p.second];~i;i=ne[i])
		{
			int j=e[i];
			if(dist[j][0]>p.first+w[i])
			{
				dist[j][1]=dist[j][0];
				dist[j][0]=p.first+w[i];
				pq.push(make_pair(dist[j][1],j));
			}
			else if(dist[j][1]>p.first+w[i])
			{
				dist[j][1]=p.first+w[i];
				pq.push(make_pair(dist[j][1],j));
			}
		}
	}
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 5 ms 3276 KB Output is correct
14 Correct 2 ms 2712 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 5 ms 3276 KB Output is correct
14 Correct 2 ms 2712 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 741 ms 65484 KB Output is correct
17 Correct 97 ms 16592 KB Output is correct
18 Correct 116 ms 17192 KB Output is correct
19 Correct 814 ms 69676 KB Output is correct
20 Correct 355 ms 61324 KB Output is correct
21 Correct 42 ms 8572 KB Output is correct
22 Incorrect 354 ms 56028 KB Output isn't correct