oj.uz

Submission #296932

# Submission time Handle Problem Language Result Execution time Memory
296932 2020-09-11T05:14:52 Z Hemimor Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 653 ms 51784 KB 
#include "crocodile.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<pii,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	vvp g(N);
	for(int i=0;i<M;i++){
		int u=R[i][0],v=R[i][1];
		g[u].push_back({v,L[i]});
		g[v].push_back({u,L[i]});
	}
	vl c(N,INF),d(N,INF);
	priority_queue<pll> q;
	for(int i=0;i<K;i++){
		d[P[i]]=0;
		q.push({0,P[i]});
	}
	while(!q.empty()){
		auto p=q.top();q.pop();
		ll v=p.second;
		if(d[v]!=-p.first) continue;
		if(v==0) return d[v];
		for(auto pp:g[v]){
			ll u=pp.first,w=pp.second,t=d[v]+w;
			if(t<d[u]){
				if(t<c[u]){
					d[u]=c[u];
					c[u]=t;
				}
				else d[u]=t;
				q.push({-d[u],u});
			}
		}
	}
	return -1;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 5 ms 744 KB Output is correct
13 Correct 4 ms 800 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 5 ms 744 KB Output is correct
13 Correct 4 ms 800 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 546 ms 43116 KB Output is correct
17 Correct 103 ms 13424 KB Output is correct
18 Correct 112 ms 13808 KB Output is correct
19 Correct 653 ms 51784 KB Output is correct
20 Correct 330 ms 34296 KB Output is correct
21 Correct 46 ms 5496 KB Output is correct
22 Incorrect 363 ms 31096 KB Output isn't correct