oj.uz

Submission #94007

# Submission time Handle Problem Language Result Execution time Memory
94007 2019-01-14T15:12:33 Z fjzzq2002 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 629 ms 54136 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 2000555
typedef pair<int,int> pii;
typedef long long ll;
#define fi first
#define se second
namespace Wrap
{
Edgc
int g[SZ],cn[SZ];
}
int travel_plan(int N, int M_, int R[][2], int L[], int K, int P[])
{
	using namespace Wrap;
	for(int i=0;i<M_;++i)
		adde(R[i][0],R[i][1],L[i]);
	priority_queue<pii,vector<pii>,greater<pii> > pq;
	for(int i=0;i<K;++i)
	{
		int x=P[i]; cn[x]=3;
		for esb(x,e,b)
			pq.push(pii(vc[e],b));
		if(x==0) return 0;
	}
	while(!pq.empty())
	{
		pii x=pq.top(); pq.pop();
		if(cn[x.se]>=2) continue;
		++cn[x.se];
		if(cn[x.se]<2) continue;
		g[x.se]=x.fi;
		if(x.se==0) return x.fi;
		for esb(x.se,e,b)
			pq.push(pii(x.fi+vc[e],b));
	}
	return -1;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 708 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 7 ms 1244 KB Output is correct
13 Correct 4 ms 888 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 708 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 7 ms 1244 KB Output is correct
13 Correct 4 ms 888 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 629 ms 54136 KB Output is correct
17 Correct 82 ms 10104 KB Output is correct
18 Correct 82 ms 10712 KB Output is correct
19 Correct 563 ms 46708 KB Output is correct
20 Correct 253 ms 37076 KB Output is correct
21 Correct 41 ms 5240 KB Output is correct
22 Correct 548 ms 34288 KB Output is correct