oj.uz

Submission #432016

# Submission time Handle Problem Language Result Execution time Memory
432016 2021-06-17T19:07:50 Z pauloamed Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 311600 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

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 i = 0; i < m; ++i){
    // c[j][j]: intersec entre i e j
    for(int j = 0; j < i; ++j){
      for(auto x : startsAt[j]){
        if(x.first >= i) c[j][i] += x.second;
      }
      if(j) c[j][i] += c[j - 1][i];
    }
  }

  // for(int i = 0; i < m; ++i){
  //   for(int j = 0; j < m; ++j){
  //     cout << c[i][j] << " ";
  //   }cout << endl;
  // }


  for(int i = 0; i < m; ++i){
    pd[0][i] = c[i][i];
    // cout << pd[0][i] << endl;
  }
  for(int i = 1; i < m; ++i){
    solve(i, 0, m - 1, 0, m - 1);
  }

  for(int i = 0; i < m; ++i){
    int ans = 0;
    for(int j = 0; j < m; ++j){

      // cout << pd[i][j] << " ";
      ans = max(ans, pd[i][j]);
    }
    // cout << endl;
    cout << ans << "\n";
  }



}

Compilation message

nafta.cpp: In member function 'int DSU::find(int)':
nafta.cpp:26:9: warning: variable 'next' set but not used [-Wunused-but-set-variable]
   26 |     int next; // backup do pai
      |         ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16460 KB Output is correct
2 Correct 10 ms 16460 KB Output is correct
3 Correct 8 ms 16332 KB Output is correct
4 Correct 9 ms 16460 KB Output is correct
5 Correct 10 ms 16468 KB Output is correct
6 Correct 9 ms 16460 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16460 KB Output is correct
2 Correct 10 ms 16460 KB Output is correct
3 Correct 8 ms 16332 KB Output is correct
4 Correct 9 ms 16460 KB Output is correct
5 Correct 10 ms 16468 KB Output is correct
6 Correct 9 ms 16460 KB Output is correct
7 Correct 42 ms 23388 KB Output is correct
8 Correct 37 ms 22492 KB Output is correct
9 Correct 28 ms 21120 KB Output is correct
10 Correct 42 ms 23320 KB Output is correct
11 Correct 36 ms 23044 KB Output is correct
12 Correct 37 ms 23176 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16460 KB Output is correct
2 Correct 10 ms 16460 KB Output is correct
3 Correct 8 ms 16332 KB Output is correct
4 Correct 9 ms 16460 KB Output is correct
5 Correct 10 ms 16468 KB Output is correct
6 Correct 9 ms 16460 KB Output is correct
7 Correct 42 ms 23388 KB Output is correct
8 Correct 37 ms 22492 KB Output is correct
9 Correct 28 ms 21120 KB Output is correct
10 Correct 42 ms 23320 KB Output is correct
11 Correct 36 ms 23044 KB Output is correct
12 Correct 37 ms 23176 KB Output is correct
13 Execution timed out 1114 ms 311600 KB Time limit exceeded
14 Halted 0 ms 0 KB -