Submission #432063

#	Time	Username	Problem	Language	Result	Execution time	Memory
432063		pauloamed	Nafta (COI15_nafta)	C++14	34 / 100	1101 ms	311560 KiB

nafta

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

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()){
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

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