oj.uz

Submission #438046

# Submission time Handle Problem Language Result Execution time Memory
438046 2021-06-27T13:22:22 Z adamjinwei Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 696 ms 57316 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++;
}
int travel_plan(int N,int M,int R[][2],int L[],int K,int 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 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1468 KB Output is correct
4 Correct 2 ms 1588 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1468 KB Output is correct
4 Correct 2 ms 1588 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 3 ms 1740 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 5 ms 1996 KB Output is correct
13 Correct 4 ms 1868 KB Output is correct
14 Correct 2 ms 1484 KB Output is correct
15 Correct 3 ms 1612 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1468 KB Output is correct
4 Correct 2 ms 1588 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 2 ms 1484 KB Output is correct
9 Correct 3 ms 1740 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 5 ms 1996 KB Output is correct
13 Correct 4 ms 1868 KB Output is correct
14 Correct 2 ms 1484 KB Output is correct
15 Correct 3 ms 1612 KB Output is correct
16 Correct 670 ms 54972 KB Output is correct
17 Correct 92 ms 12860 KB Output is correct
18 Correct 102 ms 13488 KB Output is correct
19 Correct 696 ms 57316 KB Output is correct
20 Correct 338 ms 49740 KB Output is correct
21 Correct 38 ms 6440 KB Output is correct
22 Incorrect 324 ms 47676 KB Output isn't correct