Submission #1101798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101798		BLOBVISGOD	Nafta (COI15_nafta)	C++17	34 / 100	1043 ms	71636 KiB

nafta

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct DSU{
    int components;
    vi par, len;
    DSU(int n) : par(n,-1), len(n,1), components(n) {}
    int find(int at){
        return par[at]<0?at:(par[at]=find(par[at]));
    }
    bool unite(int a, int b){
        a = find(a), b = find(b);
        if (a==b) return 0;
        if (len[a]<len[b]) swap(a,b);
        len[a]+=len[b];
        par[b] = a;
        components--;
        return 1;
    }
    bool connected(int a, int b){
        return find(a)==find(b);
    }
};

template<typename T>
void cmax(T& a, T b){
    a = max(a,b);
}

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,m; cin >> n >> m;
    DSU dsu(n*m);

    vector<string> inp(n);
    auto inside = [&](int x, int y) -> bool {
        return x>=0 and x < n and y >=0 and y < m;
    };
    auto connect  = [&](int x1, int y1, int x2, int y2) -> void {
        if (!inside(x2,y2))
            return;
        if (inp[x2][y2] != '.') 
            dsu.unite(x1*m+y1, x2*m+y2);
    };
    rep(i,0,n) cin >> inp[i];
    rep(i,0,n) rep(j,0,m){
        if (inp[i][j] != '.'){
            connect(i,j,i,j-1);
            connect(i,j,i,j+1);
            connect(i,j,i-1,j);
            connect(i,j,i+1,j);
        }
    }

    int cc = 1;
    vi cnt(n*m);
    rep(i,0,n) rep(j,0,m){
        if (inp[i][j] != '.'){
            int par = dsu.find(i*m+j);
            cnt[par] += inp[i][j] - '0';
        }
    }

    vector<bool> vis(n*m);
    vvi trans(m,vi(m));
    rep(i,0,m){
        vi comps;
        rep(j,0,n) if (inp[j][i] != '.') comps.push_back(dsu.find(j*m+i));
        sort(all(comps));
        comps.erase(unique(all(comps)),end(comps));
        rep(j,i+1,m){
            rep(k,0,n) if (inp[k][j]!='.'){
                int par = dsu.find(k*m+j);
                if (!vis[par] and !binary_search(all(comps),par)) trans[i][j] += cnt[par], vis[par] = 1;
            }rep(k,0,n) if (inp[k][j]!='.'){
                int par = dsu.find(k*m+j);
                vis[par] = 0;
            }
        }
    }

    vector<ll> dp(m);
    rep(i,0,m){
        rep(j,0,n){
            int par = dsu.find(j*m+i);
            if (!vis[par]) vis[par] = 1, dp[i] += cnt[par];
        }rep(j,0,n){
            int par = dsu.find(j*m+i);
            vis[par] = 0;
        }
    }

    rep(i,0,m){
        ll print = 0;
        rep(j,0,m) cmax(print,dp[j]); 
        cout << print << '\n';
        if (i+1==m) break;

        auto ndp = dp;

        auto rec = [&](int l, int r, int dl, int dr, auto&& rec) -> void {
            int mid = (l+r)/2;
            ll best = -1, loc; 
            rep(from,dl,min(dr,mid)) if (dp[from] + trans[from][mid] > best){
                best = dp[from] + trans[from][mid];
                loc = from;
            }
            ndp[mid] = best;
            if (l+1>=r) return;
            rec(l,mid,dl,loc+1,rec);
            rec(mid+1,r,loc,dr,rec);
        };
        rec(i+1,m,0,m,rec);
        dp = ndp;
    }
}

Compilation message (stderr)

nafta.cpp: In constructor 'DSU::DSU(int)':
nafta.cpp:13:13: warning: 'DSU::len' will be initialized after [-Wreorder]
   13 |     vi par, len;
      |             ^~~
nafta.cpp:12:9: warning:   'int DSU::components' [-Wreorder]
   12 |     int components;
      |         ^~~~~~~~~~
nafta.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     DSU(int n) : par(n,-1), len(n,1), components(n) {}
      |     ^~~
nafta.cpp: In function 'int main()':
nafta.cpp:63:9: warning: unused variable 'cc' [-Wunused-variable]
   63 |     int cc = 1;
      |         ^~
nafta.cpp: In lambda function:
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:118:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp: In function 'int main()':
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:118:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:118:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:118:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:118:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:118:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:119:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~

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