oj.uz

Submission #995559

# Submission time Handle Problem Language Result Execution time Memory
995559 2024-06-09T10:50:12 Z Nurislam Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 388 ms 71192 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
//#define int long long
#define Mp make_pair
//#define double double long
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
const int maxN = 1e6, inf = 1e9, mod = 1e9+7;
#include "crocodile.h"
//#include "grader.cpp"
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	vii g[n];
	for(int i = 0; i < m; i++){
		g[r[i][0]].pb({l[i], r[i][1]});
		g[r[i][1]].pb({l[i], r[i][0]});
	}
	for(int i = 0; i < n; i++)sort(all(g[i]));
	priority_queue<pii, vii, greater<pii>> q;
	int us[n]{};
	for(int i = 0; i < k; i++){
		us[p[i]] = 1;
		q.push({0, p[i]});
	}
	while(!q.empty()){
		auto [dis, x] = q.top();
		q.pop();
		us[x]++;
		//cout << x << '\n';
		if(us[x] == 2){
			if(x == 0)return dis;
			
			for(auto [ct, to]:g[x]){
				if(us[to] == 2)continue;
				q.push({dis+ct, to});
			}
			
		}
	}
	return 0;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 365 ms 71192 KB Output is correct
17 Correct 58 ms 13476 KB Output is correct
18 Correct 57 ms 14932 KB Output is correct
19 Correct 337 ms 66904 KB Output is correct
20 Correct 265 ms 47408 KB Output is correct
21 Correct 30 ms 5972 KB Output is correct
22 Correct 388 ms 44836 KB Output is correct