Submission #235739

#	Time	Username	Problem	Language	Result	Execution time	Memory
235739		Dilshod_Imomov	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	6 ms	2688 KiB

crocodile

#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
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11