Submission #1101803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101803		BLOBVISGOD	Nafta (COI15_nafta)	C++17	100 / 100	356 ms	122816 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);
    vector<array<int,3>> segs;
    vi minc(n*m,m), maxc(n*m);
    rep(i,0,n) rep(j,0,m) if (inp[i][j] != '.'){
        int par = dsu.find(i*m+j);
        minc[par] = min(minc[par],j);
        cmax(maxc[par],j+1);
    }
    rep(i,0,n*m) if (maxc[i]) segs.push_back({minc[i],maxc[i], i});
    vector<vector<ll>> trans(m+1,vector<ll>(m+1));
    auto add = [&](int x1, int x2, int y1, int y2, ll v) -> void {
        trans[x1][y1] += v;
        trans[x1][y2] -= v;
        trans[x2][y1] -= v;
        trans[x2][y2] += v;
    };
    for(auto [l,r,i] : segs){
        ll v = cnt[i];
        add(0,l,l,r,v);
    }

    rep(i,0,m) rep(j,0,m) trans[i][j+1] += trans[i][j];
    rep(i,0,m) rep(j,0,m) trans[i+1][j] += trans[i][j];
    
    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:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:124:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp: In function 'int main()':
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~
nafta.cpp:124:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:124:29: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |             rec(l,mid,dl,loc+1,rec);
      |                          ~~~^~
nafta.cpp:125:16: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |             rec(mid+1,r,loc,dr,rec);
      |             ~~~^~~~~~~~~~~~~~~~~~~~

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