| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 432063 |
2021-06-17T20:02:47 Z |
pauloamed |
Nafta (COI15_nafta) |
C++14 |
|
1000 ms |
311560 KB |
#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define pii pair<int,int>
#define ppiii pair<pii,int>
#define FF first.first
#define FS first.second
#define MAXN 2010
#define all(cont) cont.begin(),cont.end()
struct DSU{
vector<int> sizes, parents;
DSU(int n){
sizes = parents = vector<int>(n);
for(int i = 0; i < n; ++i){
sizes[i] = 1;
parents[i] = i;
}
}
int find(int current){
int newRoot = current; // variavel para guardar nova raiz
while(newRoot != parents[newRoot]) // enquanto nao encontro no raiz
newRoot = parents[newRoot]; // subo na arvore
// compressao de caminho (*) REMOVER SE FOR ROLLBACK
int next; // backup do pai
while(parents[current] != newRoot){ // enquanto nao acho a nova raiz
next = parents[current]; // faco o backup do pai
parents[current] = newRoot; // digo que o pai eh a raiz achada (*)
}
return newRoot; // retornamo a raiz da arvore
}
void onion(int a, int b){
a = find(a); b = find(b); // unimos uma raiz a outra
if(a == b) return; // se for a mesma raiz, nao tenho o que unir
if(sizes[a] < sizes[b]) swap(a,b); // quero unir "b" a "a"
sizes[a] += sizes[b]; // atualizando tamanho de "a"
parents[b] = a; // pai de "b" eh "a"
}
};
int c[MAXN][MAXN];
int pd[MAXN][MAXN];
int getc(int i, int j, int k){
if(i > j) return -2;
int myc = c[j][j];
int interc = c[k][j];
return pd[i - 1][k] + myc - interc;
}
void solve(int i, int l, int r, int searchL, int searchR){
if(l > r) return;
int j = (l + r) / 2;
if(pd[i][j] == -1){
int validR = min(j, searchR);
if(searchL > validR){
pd[i][j] = -2;
}else{
auto best = MP(getc(i, j, validR), validR);
for(int k = searchL; k < validR; ++k){
best = max(best, MP(getc(i, j, k), k));
}
pd[i][j] = best.first;
solve(i, l, j - 1, searchL, best.second);
solve(i, j + 1, r, best.second, searchR);
}
}
}
int main(){
iostream::sync_with_stdio(false);
memset(pd, -1, sizeof pd);
int n, m; cin >> n >> m;
DSU dsu(n * m + 1);
vector<vector<int>> g(n, vector<int>(m, -1));
vector<int> l(n * m, m + 1);
vector<int> r(n * m, 0);
vector<int> p(n * m, 0);
for(int i = 0; i < n; ++i){
string s; cin >> s;
for(int j = 0; j < m; ++j){
int x = i * m + j;
if(s[j] == '.') continue;
g[i][j] = s[j] - '0';
if(i > 0 && g[i - 1][j] >= 0) dsu.onion(x, x - m);
if(j > 0 && g[i][j - 1] >= 0) dsu.onion(x, x - 1);
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
int x = i * m + j;
int rangeId = dsu.find(x);
l[rangeId] = min(l[rangeId], j);
r[rangeId] = max(r[rangeId], j);
p[rangeId] += g[i][j];
}
}
for(int j = 0; j < m; ++j){
unordered_set<int> vis;
for(int i = 0; i < n; ++i){
if(g[i][j] == -1) continue;
int x = i * m + j;
int rangeId = dsu.find(x);
if(vis.count(rangeId)) continue;
vis.insert(rangeId);
c[j][j] += p[rangeId];
}
}
unordered_set<int> vis;
vector<pii> startsAt[m];
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
int x = dsu.find(i * m + j);
if(vis.count(x) == 0){
startsAt[l[x]].push_back({r[x], p[x]});
vis.insert(x);
}
}
}
for(int j = 0; j < m; ++j){
sort(startsAt[j].begin(), startsAt[j].end());
int accu = 0; for(auto x : startsAt[j]) accu += x.second;
int curr = 0;
for(int i = j + 1; i < m; ++i){
while(curr < startsAt[j].size()){
if(i > startsAt[j][curr].first){
accu -= startsAt[j][curr++].second;
}else break;
}
c[j][i] += accu;
if(j) c[j][i] += c[j - 1][i];
}
pd[0][j] = c[j][j];
}
for(int i = 0; i < m; ++i){
solve(i, 0, m - 1, 0, m - 1);
int ans = 0;
for(int j = 0; j < m; ++j){
ans = max(ans, pd[i][j]);
}
cout << ans << "\n";
}
}
Compilation message
nafta.cpp: In member function 'int DSU::find(int)':
nafta.cpp:27:9: warning: variable 'next' set but not used [-Wunused-but-set-variable]
27 | int next; // backup do pai
| ^~~~
nafta.cpp: In function 'int main()':
nafta.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | while(curr < startsAt[j].size()){
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16460 KB |
Output is correct |
| 2 |
Correct |
8 ms |
16460 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
16460 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16460 KB |
Output is correct |
| 6 |
Correct |
9 ms |
16460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16460 KB |
Output is correct |
| 2 |
Correct |
8 ms |
16460 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
16460 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16460 KB |
Output is correct |
| 6 |
Correct |
9 ms |
16460 KB |
Output is correct |
| 7 |
Correct |
36 ms |
23312 KB |
Output is correct |
| 8 |
Correct |
30 ms |
22456 KB |
Output is correct |
| 9 |
Correct |
22 ms |
21160 KB |
Output is correct |
| 10 |
Correct |
29 ms |
23344 KB |
Output is correct |
| 11 |
Correct |
26 ms |
23124 KB |
Output is correct |
| 12 |
Correct |
26 ms |
23132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16460 KB |
Output is correct |
| 2 |
Correct |
8 ms |
16460 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
16460 KB |
Output is correct |
| 5 |
Correct |
10 ms |
16460 KB |
Output is correct |
| 6 |
Correct |
9 ms |
16460 KB |
Output is correct |
| 7 |
Correct |
36 ms |
23312 KB |
Output is correct |
| 8 |
Correct |
30 ms |
22456 KB |
Output is correct |
| 9 |
Correct |
22 ms |
21160 KB |
Output is correct |
| 10 |
Correct |
29 ms |
23344 KB |
Output is correct |
| 11 |
Correct |
26 ms |
23124 KB |
Output is correct |
| 12 |
Correct |
26 ms |
23132 KB |
Output is correct |
| 13 |
Execution timed out |
1101 ms |
311560 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
