oj.uz

Submission #732244

# Submission time Handle Problem Language Result Execution time Memory
732244 2023-04-28T19:28:58 Z vjudge1 Emacs (COCI20_emacs) C++17
50 / 50
 1 ms 340 KB 
// author: MisterReaper (Ahmet Alp Orakci)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
    #include "debug.h"
    #define OPEN freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    #define TIME cerr << "\n" << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds ";
#else
    #define debug(...) void(23)
    #define OPEN void(0000)
    #define TIME void(232323233)
#endif

struct DSU
{
    vector <int> par;

    DSU(int n, int m) 
    {
        par.resize(n * m);
        iota(par.begin(), par.end(), 0ll);
    }

    int get(int a)
    {
        if(par[a] == a) return a;
        return par[a] = get(par[a]);
    }

    void unite(int a, int b)
    {
        a = get(a); b = get(b);
        if(a == b) return;

        par[a] = b;
    }
};

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void solve()
{
    int n, m; cin >> n >> m;
    vector <vector <char>> arr(n +2, vector <char> (m + 2, '.'));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }

    DSU dsu(n + 2, m +2);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(arr[i][j] == '.') continue;
            for(int k = 0; k < 4; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if(arr[x][y] == '.') continue;

                dsu.unite(i * m + j, x * m + y);
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(arr[i][j] != '.' && dsu.get(i * m + j) == i * m + j)
            {
                debug(i, j, dsu.get(i * m + j));
                ans++;
            }
        }
    }

    cout << ans;
    
    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }

    TIME;

    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct