Submission #232315

#	Time	Username	Problem	Language	Result	Execution time	Memory
232315		TempoTemp	Raspad (COI17_raspad)	C++14	100 / 100	1546 ms	10744 KiB

raspad

// Pied!
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, M = 53;
int n, m, P[M * 2];
char S[N][M];
int Find(int v)
{
    return P[v] < 0 ? v : (P[v] = Find(P[v]));
}
inline bool Merge(int v, int u)
{
    v = Find(v);
    u = Find(u);
    if (v == u)
        return 0;
    if (v > u)
        swap(v, u);
    P[u] = v;
    return 1;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        scanf("%s", &S[i][1]);
    long long tot = 0;
    vector < vector < int > > A, B;
    for (int i = 1; i <= n; i ++)
    {
        int Cnt = 0;
        vector < int > R(m + 1, 0);
        for (int j = 1; j <= m; j ++)
            if (S[i][j] == '1')
                R[j] = S[i][j - 1] == '1' ? R[j - 1] : ++ Cnt;
        tot += 1LL * i * (n - i + 1) * Cnt;
        R[0] = 1;
        B.push_back(R);
        for (auto st : A)
        {
            int Cn = 0;
            memset(P, -1, sizeof(P));
            for (int j = 1; j <= m; j ++)
                if (st[j] && R[j])
                    Cn += Merge(R[j], st[j] + Cnt);
            vector < int > T(m + 1, 0);
            for (int j = 1; j <= m; j ++)
                T[j] = Find(R[j]);
            T[0] = st[0];
            B.push_back(T);
            tot -= 1LL * Cn * st[0] * (n - i + 1);
        }
        for (int h = 0; h + 1 < (int)B.size(); h ++)
        {
            bool ff = 0;
            for (int j = 1; j <= m && !ff; j ++)
                ff |= B[h][j] != B[h + 1][j];
            if (ff) continue;
            B[h][0] += B[h + 1][0];
            B.erase(B.begin() + h + 1);
        }
        A.swap(B);
        B.clear();
    }
    return !printf("%lld\n", tot);
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:24: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:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &S[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~

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