Submission #850591

# Submission time Handle Problem Language Result Execution time Memory
850591 2023-09-17T03:13:46 Z hqminhuwu Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
429 ms 86076 KB
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <ll,ll>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e16;
const ll mod = 1e9 + 7;

priority_queue <pll,vector<pll>,greater<pll>> q;
int n,m,k,i,u,v,w;
pll d[N];
vector <pll> a[N];
bool vis[N];
ll travel_plan (int nn, int mm, int r[][2], int l[], int kk, int p[]){
	//ios_base::sync_with_stdio(0); cin.tie(0);
	n = nn;
	m = mm;
	k = kk;
	forr (i,0,m - 1){
		u = r[i][0], v = r[i][1], w = l[i];
		a[u].pb({v,w});
		a[v].pb({u,w});
	}
	forr (i,0,n - 1)
		d[i] = {oo,oo};
	forr (i,0,k - 1)
		u = p[i], q.push({0,u}),d[u] = {0,0};
	while (!q.empty()){
		pii u = q.top();
		q.pop();
		if (vis[u.nd])
			continue;
		vis[u.nd] = 1;
		//cout << u.st << " " << u.nd << "\n";
		for (pll v : a[u.nd]){
			ll cost = u.st + v.nd;
			//cout << cost << "\n";
			if (cost < d[v.st].st){
				d[v.st].nd = d[v.st].st;
				d[v.st].st = cost;
				//if (d[v.st].nd != oo) 
					q.push({d[v.st].nd,v.st});
			}
			else if (cost < d[v.st].nd){
				d[v.st].nd = cost;
				q.push({cost,v.st});
			}
		}
	}
	return d[0].nd;
}
/*



*/

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10788 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10788 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 5 ms 13144 KB Output is correct
14 Correct 3 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10788 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 4 ms 12888 KB Output is correct
10 Correct 2 ms 10584 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 5 ms 13144 KB Output is correct
14 Correct 3 ms 10584 KB Output is correct
15 Correct 2 ms 10584 KB Output is correct
16 Correct 325 ms 78016 KB Output is correct
17 Correct 72 ms 24640 KB Output is correct
18 Correct 86 ms 26824 KB Output is correct
19 Correct 429 ms 86076 KB Output is correct
20 Correct 222 ms 63688 KB Output is correct
21 Correct 34 ms 19404 KB Output is correct
22 Correct 243 ms 59604 KB Output is correct