oj.uz

Submission #79781

# Submission time Handle Problem Language Result Execution time Memory
79781 2018-10-16T11:09:51 Z antimirage Dango Maker (JOI18_dango_maker) C++17
13 / 100
 72 ms 71352 KB 
#include <bits/stdc++.h>

#define pb emplace_back

using namespace std;

const int N = 3005;

int n, m, d[2][N][N], sz, u[3000005], wh, bl, ans,  used[3000005], dp[3000005][2];

char ar[N][N];

vector <int> g[3000005], vec;

void dfs1 (int v, int color)
{
    if (color == 0) wh++;
    else bl++;
    u[v] = 1;

    for (auto to : g[v])
    {
        if (!u[to])
            dfs1(to, color ^ 1);
    }
}
bool fl;

void check(int v, int p)
{
    vec.push_back(v);

    used[v] = 1;

    for (auto to : g[v])
    {
        if (to == p) continue;
        if (used[to])
            fl = false;
        else
            check(to, v);
    }
}
void dfs2 (int v, int p)
{
    u[v] = 1;

    int sum1 = 1, sum2 = 0;

    for (auto to : g[v])
    {
        if (to == p) continue;
        dfs2(to, v);

        sum1 += dp[to][0];
        sum2 += max(dp[to][0], dp[to][1]);
    }
    dp[v][0] = sum2;
    dp[v][1] = sum1;
}
main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        scanf("\n");
        for (int j = 1; j <= m; j++)
            scanf("%c", &ar[i][j]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if ( j + 2 <= m && ar[i][j] == 'R' && ar[i][j + 1] == 'G' && ar[i][j + 2] == 'W' )
                d[0][i][j] = ++sz;
            if ( i + 2 <= n && ar[i][j] == 'R' && ar[i + 1][j] == 'G' && ar[i + 2][j] == 'W')
                d[1][i][j] = ++sz;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if ( d[0][i][j] )
            {
                if (d[1][i][j])
                    g[ d[0][i][j] ].pb( d[1][i][j] );

                if (d[1][i - 1][j + 1])
                    g[ d[0][i][j] ].pb( d[1][i - 1][j + 1] );

                if (d[1][i - 2][j + 2])
                    g[ d[0][i][j] ].pb( d[1][i - 2][j + 2] );
            }
            if ( d[1][i][j] )
            {
                if (d[0][i][j])
                    g[ d[1][i][j] ].pb( d[0][i][j] );

                if (d[0][i + 1][j - 1])
                    g[ d[1][i][j] ].pb( d[0][i + 1][j - 1] );

                if (d[0][i + 2][j - 2])
                    g[ d[1][i][j] ].pb( d[0][i + 2][j - 2] );
            }
        }
    }
    for (int i = 1; i <= sz; i++)
    {
        if (u[i]) continue;
        vec.clear();
        fl = 1;

        check(i, 0);

        if (fl)
        {
            dfs2(i, 0);
            ans += max(dp[i][0], dp[i][1]);
        }
        else
        {
            wh = bl = 0;
            dfs1(i, 0);
            ans += max( wh, bl );
        }
        for (auto to : vec)
            used[to] = dp[to][0] = dp[to][1] = 0;
    }
    cout << ans << endl;
}
/**
7 7
RRRRRGW
RRRRGWR
RRRGWRR
RRGRRRR
RGWRRRR
GWRRRRR
WRRRRRR
**/

Compilation message

dango_maker.cpp:61:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
dango_maker.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &ar[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 66 ms 70912 KB Output is correct
3 Correct 64 ms 70912 KB Output is correct
4 Correct 69 ms 70912 KB Output is correct
5 Correct 68 ms 70960 KB Output is correct
6 Correct 67 ms 71004 KB Output is correct
7 Correct 65 ms 71004 KB Output is correct
8 Correct 62 ms 71004 KB Output is correct
9 Correct 64 ms 71004 KB Output is correct
10 Correct 66 ms 71148 KB Output is correct
11 Correct 66 ms 71148 KB Output is correct
12 Correct 64 ms 71148 KB Output is correct
13 Correct 64 ms 71148 KB Output is correct
14 Correct 68 ms 71148 KB Output is correct
15 Correct 70 ms 71148 KB Output is correct
16 Correct 68 ms 71168 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 66 ms 70912 KB Output is correct
3 Correct 64 ms 70912 KB Output is correct
4 Correct 69 ms 70912 KB Output is correct
5 Correct 68 ms 70960 KB Output is correct
6 Correct 67 ms 71004 KB Output is correct
7 Correct 65 ms 71004 KB Output is correct
8 Correct 62 ms 71004 KB Output is correct
9 Correct 64 ms 71004 KB Output is correct
10 Correct 66 ms 71148 KB Output is correct
11 Correct 66 ms 71148 KB Output is correct
12 Correct 64 ms 71148 KB Output is correct
13 Correct 64 ms 71148 KB Output is correct
14 Correct 68 ms 71148 KB Output is correct
15 Correct 70 ms 71148 KB Output is correct
16 Correct 68 ms 71168 KB Output is correct
17 Correct 67 ms 71168 KB Output is correct
18 Correct 63 ms 71168 KB Output is correct
19 Correct 68 ms 71168 KB Output is correct
20 Correct 64 ms 71332 KB Output is correct
21 Correct 67 ms 71352 KB Output is correct
22 Correct 68 ms 71352 KB Output is correct
23 Correct 67 ms 71352 KB Output is correct
24 Correct 63 ms 71352 KB Output is correct
25 Correct 69 ms 71352 KB Output is correct
26 Correct 67 ms 71352 KB Output is correct
27 Correct 63 ms 71352 KB Output is correct
28 Correct 68 ms 71352 KB Output is correct
29 Correct 68 ms 71352 KB Output is correct
30 Correct 72 ms 71352 KB Output is correct
31 Correct 66 ms 71352 KB Output is correct
32 Correct 67 ms 71352 KB Output is correct
33 Correct 67 ms 71352 KB Output is correct
34 Incorrect 68 ms 71352 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 66 ms 70912 KB Output is correct
3 Correct 64 ms 70912 KB Output is correct
4 Correct 69 ms 70912 KB Output is correct
5 Correct 68 ms 70960 KB Output is correct
6 Correct 67 ms 71004 KB Output is correct
7 Correct 65 ms 71004 KB Output is correct
8 Correct 62 ms 71004 KB Output is correct
9 Correct 64 ms 71004 KB Output is correct
10 Correct 66 ms 71148 KB Output is correct
11 Correct 66 ms 71148 KB Output is correct
12 Correct 64 ms 71148 KB Output is correct
13 Correct 64 ms 71148 KB Output is correct
14 Correct 68 ms 71148 KB Output is correct
15 Correct 70 ms 71148 KB Output is correct
16 Correct 68 ms 71168 KB Output is correct
17 Correct 67 ms 71168 KB Output is correct
18 Correct 63 ms 71168 KB Output is correct
19 Correct 68 ms 71168 KB Output is correct
20 Correct 64 ms 71332 KB Output is correct
21 Correct 67 ms 71352 KB Output is correct
22 Correct 68 ms 71352 KB Output is correct
23 Correct 67 ms 71352 KB Output is correct
24 Correct 63 ms 71352 KB Output is correct
25 Correct 69 ms 71352 KB Output is correct
26 Correct 67 ms 71352 KB Output is correct
27 Correct 63 ms 71352 KB Output is correct
28 Correct 68 ms 71352 KB Output is correct
29 Correct 68 ms 71352 KB Output is correct
30 Correct 72 ms 71352 KB Output is correct
31 Correct 66 ms 71352 KB Output is correct
32 Correct 67 ms 71352 KB Output is correct
33 Correct 67 ms 71352 KB Output is correct
34 Incorrect 68 ms 71352 KB Output isn't correct
35 Halted 0 ms 0 KB -