Submission #144947

#	Time	Username	Problem	Language	Result	Execution time	Memory
144947		SamAnd	Raspad (COI17_raspad)	C++17	26 / 100	6050 ms	2936 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 55;

int n, m;
char a[N][M];

vector<int> v[M];

int p[M];
int fi(int x)
{
    if (p[x] == 0)
        return 0;
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}
void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    p[x] = y;
}

long long ans;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf(" %s", a[i]);
    for (int i = 0; i < n; ++i)
    {
        long long yans = 0;
        int nb[M] = {};
        bool c[M] = {};
        for (int j = i; j < n; ++j)
        {
            for (int k = 1; k <= m; ++k)
                v[k].clear();
            for (int k = 1; k <= m; ++k)
            {
                if (j != i && a[j - 1][k - 1] == '1' && a[j][k - 1] == '1')
                {
                    v[nb[k]].push_back(k);
                }
            }
            for (int k = 1; k <= m; ++k)
            {
                if (c[k] && v[k].empty())
                    ++yans;
            }
            for (int k = 1; k <= m; ++k)
            {
                if (a[j][k - 1] == '1')
                    p[k] = k;
                else
                    p[k] = 0;
            }
            for (int k = 1; k <= m; ++k)
            {
                for (int vi = 0; vi < (int)v[k].size() - 1; ++vi)
                {
                    kpc(v[k][vi], v[k][vi + 1]);
                }
            }
            for (int k = 2; k <= m; ++k)
            {
                if (a[j][k - 1] == '1' && a[j][k - 2] == '1')
                    kpc(k, k - 1);
            }
            for (int k = 1; k <= m; ++k)
                nb[k] = fi(k);
            memset(c, false, sizeof c);
            for (int k = 1; k <= m; ++k)
                c[nb[k]] = true;
            for (int k = 1; k <= m; ++k)
            {
                if (c[k])
                    ++yans;
            }
            ans += yans;
            for (int k = 1; k <= m; ++k)
            {
                if (c[k])
                    --yans;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39