oj.uz

Submission #1101798

# Submission time Handle Problem Language Result Execution time Memory
1101798 2024-10-16T20:04:45 Z BLOBVISGOD Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 71636 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);
    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

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

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 220 ms 1876 KB Output is correct
8 Correct 267 ms 1876 KB Output is correct
9 Correct 168 ms 1876 KB Output is correct
10 Correct 187 ms 2132 KB Output is correct
11 Correct 133 ms 2084 KB Output is correct
12 Correct 107 ms 1876 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 220 ms 1876 KB Output is correct
8 Correct 267 ms 1876 KB Output is correct
9 Correct 168 ms 1876 KB Output is correct
10 Correct 187 ms 2132 KB Output is correct
11 Correct 133 ms 2084 KB Output is correct
12 Correct 107 ms 1876 KB Output is correct
13 Execution timed out 1043 ms 71636 KB Time limit exceeded
14 Halted 0 ms 0 KB -