oj.uz

Submission #868203

# Submission time Handle Problem Language Result Execution time Memory
868203 2023-10-30T19:01:35 Z aykhn Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 444 ms 96088 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<pair<pll, pll>> dist(n, mpr(mpr(inf, -1 * 1LL), mpr(inf, -1 * 1LL)));
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	for (ll x : p) 
	{
		dist[x] = mpr(mpr(0LL, x), mpr(0LL, x));
		pq.push(mpr(0LL, 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.se == -1)
			{
				dist[v.fi].fi.se = u;
				dist[v.fi].fi.fi = d + v.se;
			} 
			else
			{
				if (dist[v.fi].fi.fi > d + v.se)
				{
					if (dist[v.fi].fi.se == u)
					{
						dist[v.fi].fi.fi = d + v.se;
					}
					else
					{
						int prev = dist[v.fi].se.fi;
						dist[v.fi].se = dist[v.fi].fi;
						if (dist[v.fi].se.fi < prev)
						{
							pq.push(mpr(dist[v.fi].se.fi, v.fi));
						}
						dist[v.fi].fi = mpr(d + v.se, u);

					}
				}
				else if (dist[v.fi].se.fi > d + v.se && u != dist[v.fi].fi.se)
				{
					dist[v.fi].se = mpr(d + v.se, u);
					pq.push(mpr(dist[v.fi].se.fi, v.fi));
				}
			}
		}
	}
	int ans = dist[0].se.fi;
	return ans;

}

Subtask #1
46.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 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct

Subtask #2
43.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 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6784 KB Output is correct
12 Correct 4 ms 7260 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.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 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6784 KB Output is correct
12 Correct 4 ms 7260 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 365 ms 88056 KB Output is correct
17 Correct 53 ms 20816 KB Output is correct
18 Correct 68 ms 25164 KB Output is correct
19 Correct 444 ms 96088 KB Output is correct
20 Correct 222 ms 72524 KB Output is correct
21 Correct 28 ms 13188 KB Output is correct
22 Correct 248 ms 66128 KB Output is correct