| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 632728 |
2022-08-20T17:03:05 Z |
Alma |
Nafta (COI15_nafta) |
C++17 |
|
1 ms |
340 KB |
#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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
