oj.uz

Submission #868199

# Submission time Handle Problem Language Result Execution time Memory
868199 2023-10-30T18:40:07 Z aykhn Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 6768 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define bpcll __builtin_popcountll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;

ll n, m, k;
vector<ll> p;
vector<pll> adj[MXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n = N;
	m = M;
	k = K;
	for (int i = 0; i < m; i++)
	{
		adj[R[i][0]].pb(mpr(R[i][1], L[i]));
		adj[R[i][1]].pb(mpr(R[i][0], L[i]));
	}
	for (int i = 0; i < k; i++) p.pb(P[i]);
	vector<pll> dist(n + 1, mpr(infll, infll));
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	for (ll x : p) 
	{
		dist[x] = mpr(0LL, 0LL);
		pq.push(mpr(0, x));
	}
	while (!pq.empty())
	{
		ll u = pq.top().se;
		ll d = pq.top().fi;
		pq.pop();
		for (pll v : adj[u])
		{
			if (dist[v.fi].fi == inf) dist[v.fi].fi = d + v.se;
			else
			{
				if (dist[v.fi].fi > d + v.se)
				{
					dist[v.fi].se = dist[v.fi].fi;
					dist[v.fi].fi = d + v.se;
					pq.push(mpr(dist[v.fi].se, v.fi));
				}
				else if (dist[v.fi].se > d + v.se)
				{
					dist[v.fi].se = d + v.se;
					pq.push(mpr(dist[v.fi].se, v.fi));
				}
			}
		}
	}
	int ans = dist[0].se;
	return ans;
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6768 KB Output isn't correct
4 Halted 0 ms 0 KB -