oj.uz

Submission #1101803

# Submission time Handle Problem Language Result Execution time Memory
1101803 2024-10-16T20:32:13 Z BLOBVISGOD Nafta (COI15_nafta) C++17
100 / 100
 356 ms 122816 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 6 ms 3088 KB Output is correct
8 Correct 8 ms 2896 KB Output is correct
9 Correct 7 ms 2896 KB Output is correct
10 Correct 7 ms 2896 KB Output is correct
11 Correct 6 ms 2896 KB Output is correct
12 Correct 6 ms 2896 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 6 ms 3088 KB Output is correct
8 Correct 8 ms 2896 KB Output is correct
9 Correct 7 ms 2896 KB Output is correct
10 Correct 7 ms 2896 KB Output is correct
11 Correct 6 ms 2896 KB Output is correct
12 Correct 6 ms 2896 KB Output is correct
13 Correct 296 ms 120912 KB Output is correct
14 Correct 356 ms 122816 KB Output is correct
15 Correct 323 ms 119084 KB Output is correct
16 Correct 244 ms 121836 KB Output is correct
17 Correct 240 ms 119056 KB Output is correct
18 Correct 234 ms 118800 KB Output is correct