oj.uz

Submission #1081358

# Submission time Handle Problem Language Result Execution time Memory
1081358 2024-08-30T01:30:14 Z nrg_studio Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 320 ms 89292 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)

ll ans;

ll travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	ios::sync_with_stdio(false); cin.tie(0);

	vector<vector<pii>> adj(n);
	F0R(i,m) {
		adj[r[i][0]].pb({r[i][1],l[i]});
		adj[r[i][1]].pb({r[i][0],l[i]});
	}
	vector<pii> mn(n,{LLONG_MAX,LLONG_MAX});
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	F0R(i,k) {
		mn[p[i]] = {0,0};
		pq.push({0,p[i]});
	} 
	vector<bool> vis(n,false);
	while (pq.size()) {
		pii cur = pq.top(); pq.pop();
		//if (cur.f != mn[cur.s].s) {continue;}
		if (vis[cur.s]) {continue;}
		vis[cur.s] = true;


		for (pii qwerty : adj[cur.s]) {
			ll cand = qwerty.s+cur.f, x = qwerty.f;
			if (cand < mn[x].s) {
				if (cand <= mn[x].f) {
					mn[x].s = mn[x].f; mn[x].f = cand;	
				} else {mn[x].s = cand;}
				if (mn[x].s!=LLONG_MAX) {pq.push({mn[x].s,x});}
			}
		}
	} 
	ans = mn[0].s;
	//return mn[0].s << '\n';
	return ans;
}
/*
int main() {
	int n, m, k; cin >> n >> m >> k;
	int r[m][2],l[m],p[k];
	F0R(i,m) {cin >> r[i][0]>>r[i][1]>>l[i];}
	F0R(i,k) {cin >> p[i];}
	ll x = travel_plan(n,m,r,l,k,p);
	cout<<ans;
}*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 3 ms 1368 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 3 ms 1368 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 278 ms 81528 KB Output is correct
17 Correct 53 ms 17744 KB Output is correct
18 Correct 60 ms 20308 KB Output is correct
19 Correct 320 ms 89292 KB Output is correct
20 Correct 191 ms 65588 KB Output is correct
21 Correct 25 ms 8272 KB Output is correct
22 Correct 202 ms 62452 KB Output is correct