oj.uz

Submission #705489

# Submission time Handle Problem Language Result Execution time Memory
705489 2023-03-04T13:55:06 Z penguin133 Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 115 ms 262144 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int memo[100005];
vector <pi> adj[100000 + 5];
int dp(int x, int par){
	if(memo[x] != -1)return memo[x];
	int mn = 1e9, mn2 = 1e9;
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		int tmp = dp(i, x) + j;
		if(tmp < mn)mn2 = mn, mn = tmp;
		else if(mn2 > tmp)mn2 = tmp;
	}
	return memo[x] = mn2;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	
	int dist[N+5][2];
	for(int i=0;i<=N;i++)dist[i][0] = dist[i][1] = 2e9;
	for(int i=0;i<M;i++){
		adj[R[i][0]].push_back({R[i][1], L[i]});
		adj[R[i][1]].push_back({R[i][0], L[i]});
	}
	/*
	priority_queue <pi, vector<pi>, greater<pi> > pq;
	for(int i=0;i<K;i++){
		dist[P[i]][0] = dist[P[i]][1] = 0;
		pq.push({0, P[i]});
	}
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se;
		pq.pop();
		if(dist[y][1] != x)continue;
		for(auto [i, j] : adj[y]){
			if(dist[i][0] > x + j){
				dist[i][1] = dist[i][0];
				dist[i][0] = x + j;
				pq.push({dist[i][0], i});
			}
			else if(dist[i][1] > x + j){
				dist[i][1] = x + j;
				pq.push({dist[i][1], i});
			}
		}
	}
	return (dist[0][1] == 1e9 ? -1 : dist[0][1]);
	*/
	memset(memo, -1, sizeof(memo));
	for(int i=0;i<K;i++){
		memo[P[i]] = 0;
	}
	return dp(0, -1);
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3192 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3192 KB Output is correct
9 Runtime error 115 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3020 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3192 KB Output is correct
9 Runtime error 115 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -