Submission #64206

#	Time	Username	Problem	Language	Result	Execution time	Memory
64206		gs14004	물탱크 (KOI18_watertank)	C++17	100 / 100	1555 ms	189000 KiB

watertank

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 1005;

struct disj{
	int pa[1000005];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;



int n, m, h;
vector<pi> e[MAXN];
vector<pi> gph[1000005];

lint dfs(int x, int p, int e){
	lint ret = e;
	for(auto &i : gph[x]){
		if(i.second != p){
			ret += dfs(i.second, x, max(e, i.first));
		}
	}
	return ret;
}

int get(int x, int y){
	if(1 <= x && x <= n && 1 <= y && y <= m){
		return (x - 1) * m + (y - 1) + 1;
	}
	else return 0;
}

int main(){
	cin >> n >> m >> h;
	disj.init(n * m);
	for(int i=0; i<n+1; i++){
		for(int j=1; j<=m; j++){
			int l = get(i, j);
			int r = get(i + 1, j);
			int x;
			scanf("%d",&x);
			if(x == -1) x = h;
			e[x].push_back(pi(l, r));
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=0; j<m+1; j++){
			int l = get(i, j);
			int r = get(i, j + 1);
			int x;
			scanf("%d",&x);
			if(x == -1) x = h;
			e[x].push_back(pi(l, r));
		}
	}
	for(int i=0; i<=h; i++){
		for(auto &j : e[i]){
			if(disj.uni(j.first, j.second)){
				gph[j.first].push_back(pi(i, j.second));
				gph[j.second].push_back(pi(i, j.first));
			}
		}
	}
	cout << dfs(0, -1, 0) << endl;
}

Compilation message (stderr)

watertank.cpp: In function 'int main()':
watertank.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
watertank.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 18 / 18
• Subtask 3: 15 / 15
• Subtask 4: 21 / 21
• Subtask 5: 40 / 40