Submission #235746

#	Time	Username	Problem	Language	Result	Execution time	Memory
235746		Dilshod_Imomov	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	936 ms	59768 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, c = st.begin()->first;
		st.erase( st.begin() );
		// cout << v << ' ' << c << '\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];
				if ( dp[u][1] != 2e9 ) {
					st.insert( { dp[u][1], u } );
				}
				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];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:27:31: warning: unused variable 'c' [-Wunused-variable]
   int v = st.begin()->second, c = st.begin()->first;
                               ^

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11