Submission #632728

#	Time	Username	Problem	Language	Result	Execution time	Memory
632728		Alma	Nafta (COI15_nafta)	C++17	0 / 100	1 ms	340 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
using ll = long long;
using ii = pair<int,int>;

const int INF = 1e9;
const ll LLINF = 1e18;
using vi = vector<int>;
using vvi = vector<vi>;

void setIO (string fileName) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if (fileName != "std") {
        freopen((fileName + ".in").c_str(), "r", stdin);
        freopen((fileName + ".out").c_str(), "w", stdout);
    }
}

int dfs (int i, int j, int r, int c, vvi& tab, vvi& vis) {
	if (i < 0 or r <= i or j < 0 or c <= j) return 0;
	if (vis[i][j] or tab[i][j] < 0) return 0;
	vis[i][j] = true;
	int x = tab[i][j];
	x += dfs(i+1, j, r, c, tab, vis);
	x += dfs(i-1, j, r, c, tab, vis);
	x += dfs(i, j+1, r, c, tab, vis);
	x += dfs(i, j-1, r, c, tab, vis);
	return x;
}

void dfs2 (int i, int j, int r, int c, vvi& tab, vvi& vis2, vi& col, vi& xcol, int x) {
	if (i < 0 or r <= i or j < 0 or c <= j) return;
	if (vis2[i][j] or tab[i][j] < 0) return;
	vis2[i][j] = true;
	if (!xcol[j]) {
		col[j] += x;
		xcol[j] = true;
	}
	dfs2(i+1, j, r, c, tab, vis2, col, xcol, x);
	dfs2(i-1, j, r, c, tab, vis2, col, xcol, x);
	dfs2(i, j+1, r, c, tab, vis2, col, xcol, x);
	dfs2(i, j-1, r, c, tab, vis2, col, xcol, x);
}

void dfs3 (int i, int j, int r, int c, vvi& tab, vi& col, vi& xcol, map<int, unordered_set<int>, greater<int>>& m, int x) {
	if (i < 0 or r <= i or j < 0 or c <= j) return;
	if (tab[i][j] < 0) return;
	tab[i][j] = -1;
	if (!xcol[j]) {
		int val = col[j];
		m[val].erase(j);
		if (m[val].empty()) m.erase(val);
		val -= x;
		col[j] = val;
		m[val].insert(j);
		xcol[j] = true;
	}
	dfs3(i+1, j, r, c, tab, col, xcol, m, x);
	dfs3(i-1, j, r, c, tab, col, xcol, m, x);
	dfs3(i, j+1, r, c, tab, col, xcol, m, x);
	dfs3(i, j-1, r, c, tab, col, xcol, m, x);
}

int main() {
    setIO("std");

    int r, c;
	cin >> r >> c;
	vvi tab(r, vi(c, -1));
	string s;
	for (int i = 0; i < r; i++) {
		cin >> s;
		for (int j = 0; j < c; j++) {
			if (s[j] != '.') tab[i][j] = s[j] - '0'; 
		}
	}

	vi col(c, 0);
	vvi vis(r, vi(c, false)), vis2(r, vi(c, false));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (!vis[i][j] and tab[i][j] >= 0) {
				int x = dfs(i, j, r, c, tab, vis);
				vi xcol(c, false);
				dfs2(i, j, r, c, tab, vis2, col, xcol, x);
			}
		}
	}

	map<int, unordered_set<int>, greater<int>> m;
	for (int j = 0; j < c; j++) {
		m[col[j]].insert(j);
	}

	vis = vvi(r, vi(c, false));
	int ans = 0;	
	for (int k = 0; k < c; k++) {
		int val = m.begin()->first;
		int idx = *m[val].begin();
		// cerr << idx << ' ' << val << '\n';
		ans += val;
		cout << ans << '\n';

		for (int i = 0; i < r; i++) {
			if (tab[i][idx] >= 0) {
				vi xcol(c, false);
				int x = dfs(i, idx, r, c, tab, vis);
				dfs3(i, idx, r, c, tab, col, xcol, m, x);
			}
		}
		m[val].erase(idx);
		if (m[val].empty()) m.erase(val);
	}

    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'void setIO(std::string)':
nafta.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((fileName + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((fileName + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66