oj.uz

Submission #64053

# Submission time Handle Problem Language Result Execution time Memory
64053 2018-08-03T09:02:29 Z kjp4155 None (KOI18_watertank) C++17
100 / 100
 1597 ms 211032 KB 
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> Pi;

const int inf = 1e9;

int N,M,H;
// idx배열은 각 칸의 번호를 저장한다
int idx[1050][1050];
// E는 그래프를 인접 리스트의 형태로 저장한다
vector<pair<int,int>> E[1000500];
// ans는 각 노드가 최종적으로 가지게 될 물높이를 저장한다
int ans[1000500];

// 정점 a와 b를 잇는 가중치 w의 간선을 만든다 
void make_edge(int a, int b, int w){
	E[a].push_back({b,w});
	E[b].push_back({a,w});
}

int main(){
	scanf("%d%d%d",&N,&M,&H);

	// idx배열 채우기
	int timer = 0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++) idx[i][j] = ++timer;
	}
		
	// 이 시점에서 idx가 채워지지 않은 곳의 값은 모두 0 이다. 
	// 이는 외부(물높이 0)를 뜻한다.

	/* 입력 받고 간선 적절히 만들기 */
	// 1. 가로벽 
	for(int i=1;i<=N+1;i++){
		for(int j=1;j<=M;j++){
			int x; scanf("%d",&x);
			if( x == -1 ) continue;
			make_edge( idx[i][j], idx[i-1][j], x);
		}
	}

	// 2. 세로벽
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M+1;j++){
			int x; scanf("%d",&x);
			if( x == -1 ) continue;
			make_edge( idx[i][j], idx[i][j-1] , x);
		}
	}

	// 초기에 물은 모두 H만큼 차 있었다고 하자
	for(int i=0;i<=N*M;i++) ans[i] = H;

	// 외부 (0번 노드)는 물높이가 0이다
	ans[0] = 0;
	
	// priority_queue에 (물높이, 정점번호) 를 넣고, 작은 것부터 순차적으로 꺼내 본다
	// 다익스트라 알고리즘의 진행방식과 유사하다
	priority_queue<Pi, vector<Pi>, greater<Pi>> pq;
	pq.push({0, 0});

	while( !pq.empty() ){
		int h = pq.top().first, node = pq.top().second;
		pq.pop();

		if( h != ans[node] ) continue;

 		// 자신과 연결된 칸들을 업데이트 (relaxation)하고, 갱신되었다면 pq에 넣어준다
		for(Pi e : E[node]){
			int nh = max(h, e.second);
			if( nh < ans[e.first] ){
				ans[e.first] = nh;
				pq.push({ans[e.first], e.first});
			}
		}
	}


	int res = 0;
	for(int i=1;i<=N*M;i++) res += ans[i];
	printf("%d\n",res);
}

Compilation message

watertank.cpp: In function 'int main()':
watertank.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&N,&M,&H);
  ~~~~~^~~~~~~~~~~~~~~~~~~
watertank.cpp:43:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d",&x);
           ~~~~~^~~~~~~~~
watertank.cpp:52:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d",&x);
           ~~~~~^~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 24 ms 24028 KB Output is correct
3 Correct 24 ms 24028 KB Output is correct
4 Correct 24 ms 24028 KB Output is correct
5 Correct 23 ms 24084 KB Output is correct
6 Correct 24 ms 24084 KB Output is correct
7 Correct 27 ms 24084 KB Output is correct
8 Correct 28 ms 24124 KB Output is correct
9 Correct 29 ms 24312 KB Output is correct
10 Correct 29 ms 24312 KB Output is correct
11 Correct 25 ms 24312 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24312 KB Output is correct
2 Correct 28 ms 24312 KB Output is correct
3 Correct 27 ms 24312 KB Output is correct
4 Correct 27 ms 24380 KB Output is correct
5 Correct 25 ms 24408 KB Output is correct
6 Correct 24 ms 24408 KB Output is correct
7 Correct 26 ms 24408 KB Output is correct
8 Correct 25 ms 24408 KB Output is correct
9 Correct 23 ms 24408 KB Output is correct
10 Correct 24 ms 24408 KB Output is correct
11 Correct 25 ms 24408 KB Output is correct
12 Correct 29 ms 24408 KB Output is correct
13 Correct 25 ms 24480 KB Output is correct
14 Correct 26 ms 24480 KB Output is correct
15 Correct 29 ms 24480 KB Output is correct
16 Correct 24 ms 24480 KB Output is correct
17 Correct 26 ms 24480 KB Output is correct
18 Correct 24 ms 24480 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 38344 KB Output is correct
2 Correct 27 ms 38344 KB Output is correct
3 Correct 264 ms 46724 KB Output is correct
4 Correct 323 ms 68760 KB Output is correct
5 Correct 26 ms 68760 KB Output is correct
6 Correct 635 ms 90036 KB Output is correct
7 Correct 295 ms 90036 KB Output is correct
8 Correct 623 ms 109136 KB Output is correct
9 Correct 308 ms 109136 KB Output is correct
10 Correct 29 ms 109136 KB Output is correct
11 Correct 585 ms 113312 KB Output is correct
12 Correct 26 ms 113312 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 113312 KB Output is correct
2 Correct 24 ms 113312 KB Output is correct
3 Correct 29 ms 113312 KB Output is correct
4 Correct 27 ms 113312 KB Output is correct
5 Correct 28 ms 113312 KB Output is correct
6 Correct 23 ms 113312 KB Output is correct
7 Correct 25 ms 113312 KB Output is correct
8 Correct 28 ms 113312 KB Output is correct
9 Correct 28 ms 113312 KB Output is correct
10 Correct 26 ms 113312 KB Output is correct
11 Correct 24 ms 113312 KB Output is correct
12 Correct 25 ms 113312 KB Output is correct
13 Correct 26 ms 113312 KB Output is correct
14 Correct 23 ms 113312 KB Output is correct
15 Correct 26 ms 113312 KB Output is correct
16 Correct 31 ms 113312 KB Output is correct
17 Correct 27 ms 113312 KB Output is correct
18 Correct 25 ms 113312 KB Output is correct
19 Correct 26 ms 113312 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 113312 KB Output is correct
2 Correct 25 ms 113312 KB Output is correct
3 Correct 25 ms 113312 KB Output is correct
4 Correct 27 ms 113312 KB Output is correct
5 Correct 28 ms 113312 KB Output is correct
6 Correct 235 ms 113312 KB Output is correct
7 Correct 24 ms 113312 KB Output is correct
8 Correct 27 ms 113312 KB Output is correct
9 Correct 218 ms 113312 KB Output is correct
10 Correct 25 ms 113312 KB Output is correct
11 Correct 30 ms 113312 KB Output is correct
12 Correct 228 ms 113312 KB Output is correct
13 Correct 289 ms 113312 KB Output is correct
14 Correct 29 ms 113312 KB Output is correct
15 Correct 480 ms 124528 KB Output is correct
16 Correct 22 ms 124528 KB Output is correct
17 Correct 23 ms 124528 KB Output is correct
18 Correct 31 ms 124528 KB Output is correct
19 Correct 317 ms 124528 KB Output is correct
20 Correct 23 ms 124528 KB Output is correct
21 Correct 1124 ms 166416 KB Output is correct
22 Correct 23 ms 166416 KB Output is correct
23 Correct 21 ms 166416 KB Output is correct
24 Correct 22 ms 166416 KB Output is correct
25 Correct 24 ms 166416 KB Output is correct
26 Correct 23 ms 166416 KB Output is correct
27 Correct 23 ms 166416 KB Output is correct
28 Correct 570 ms 166416 KB Output is correct
29 Correct 758 ms 166416 KB Output is correct
30 Correct 360 ms 166416 KB Output is correct
31 Correct 805 ms 178200 KB Output is correct
32 Correct 519 ms 178200 KB Output is correct
33 Correct 31 ms 178200 KB Output is correct
34 Correct 414 ms 178200 KB Output is correct
35 Correct 35 ms 178200 KB Output is correct
36 Correct 32 ms 178200 KB Output is correct
37 Correct 31 ms 178200 KB Output is correct
38 Correct 975 ms 188104 KB Output is correct
39 Correct 1597 ms 206276 KB Output is correct
40 Correct 31 ms 206276 KB Output is correct
41 Correct 36 ms 206276 KB Output is correct
42 Correct 31 ms 206276 KB Output is correct
43 Correct 33 ms 206276 KB Output is correct
44 Correct 430 ms 206276 KB Output is correct
45 Correct 1396 ms 211032 KB Output is correct
46 Correct 32 ms 211032 KB Output is correct