Submission #64053

#	Time	Username	Problem	Language	Result	Execution time	Memory
64053		kjp4155	물탱크 (KOI18_watertank)	C++17	100 / 100	1597 ms	211032 KiB

watertank

#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 (stderr)

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 / 6
• Subtask 2: 18 / 18
• Subtask 3: 15 / 15
• Subtask 4: 21 / 21
• Subtask 5: 40 / 40