oj.uz

답안 #432063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432063 2021-06-17T20:02:47 Z pauloamed Nafta (COI15_nafta) C++14
34 / 100
 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()){
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 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 -