oj.uz

Submission #235739

# Submission time Handle Problem Language Result Execution time Memory
235739 2020-05-29T14:32:18 Z Dilshod_Imomov Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 6 ms 2688 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
 
const int NN = 1e5 + 7;
 
vector < pair < int, int > > adj[NN];
int dp[NN][2];
 
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for ( int i = 0; i < m; i++ ) {
		int u = R[i][0], v = R[i][1];
		adj[u].push_back( { v, L[i] } );
		adj[v].push_back( { u, L[i] } );
	}
	for ( int i = 0; i < n; i++ ) {
		dp[i][0] = dp[i][1] = 2e9;
	}
	set < pair < int, int > > st;
	for ( int i = 0; i < K; i++ ) {
		int v = P[i];
		dp[v][0] = dp[v][1] = 0;
		st.insert( { 0, v } );
	}
	while ( !st.empty() ) {
		int v = st.begin()->second;
		st.erase( st.begin() );
		// cout << v << '\n';
		for ( auto pr: adj[v] ) {
			int u = pr.first, len = pr.second;
			if ( dp[u][0] >= len + dp[v][1] ) {
				st.erase( { dp[u][1], u } );
				dp[u][1] = dp[u][0];
				dp[u][0] = len + dp[v][1];
				st.insert({ dp[u][0], u } );
			}
			else if ( dp[u][1] > len + dp[v][1] ) {
				st.erase( { dp[u][1], u } );
				dp[u][1] = len + dp[v][1];
				st.insert( { dp[u][1], u } );
			}
		}
	}
	return dp[0][1];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -