oj.uz

답안 #235746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
235746 2020-05-29T14:49:01 Z Dilshod_Imomov 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 936 ms 59768 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, 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

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.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 9 ms 2944 KB Output is correct
10 Correct 8 ms 2688 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 10 ms 3200 KB Output is correct
13 Correct 10 ms 3200 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 7 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 9 ms 2944 KB Output is correct
10 Correct 8 ms 2688 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 10 ms 3200 KB Output is correct
13 Correct 10 ms 3200 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 7 ms 2816 KB Output is correct
16 Correct 665 ms 55928 KB Output is correct
17 Correct 106 ms 13820 KB Output is correct
18 Correct 131 ms 15224 KB Output is correct
19 Correct 936 ms 59768 KB Output is correct
20 Correct 404 ms 49632 KB Output is correct
21 Correct 51 ms 7672 KB Output is correct
22 Correct 428 ms 45944 KB Output is correct