oj.uz

Submission #850592

# Submission time Handle Problem Language Result Execution time Memory
850592 2023-09-17T03:14:37 Z hqminhuwu Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 397 ms 84524 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 (u.st != d[u.nd].nd)
			continue;
		//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;
}
/*



*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 5 ms 13148 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 4 ms 13148 KB Output is correct
13 Correct 5 ms 13148 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 2 ms 10588 KB Output is correct
16 Correct 310 ms 78648 KB Output is correct
17 Correct 67 ms 24772 KB Output is correct
18 Correct 92 ms 26940 KB Output is correct
19 Correct 397 ms 84524 KB Output is correct
20 Correct 215 ms 63568 KB Output is correct
21 Correct 32 ms 19528 KB Output is correct
22 Incorrect 228 ms 59704 KB Output isn't correct
23 Halted 0 ms 0 KB -