oj.uz

Submission #791209

# Submission time Handle Problem Language Result Execution time Memory
791209 2023-07-23T16:14:52 Z n3rm1n Dango Maker (JOI18_dango_maker) C++17
13 / 100
 98 ms 211792 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 3005, MAXX = 9e6 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m;
char a[MAXN][MAXN];
int cnt;
vector < int > v[MAXX];
void read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
        {
            cin >> a[i][j];
        }
    }
}
int dir0[MAXN][MAXN], dir1[MAXN][MAXN];
int type[MAXX];
void precompute()
{
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= m-2; ++ j)
        {
            if(a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W')
            {
                cnt ++;
                //g.push_back(tri(i, j, 0, cnt));
                type[cnt] = 1;
                dir0[i][j] = cnt;
                dir0[i][j+1] = cnt;
                dir0[i][j+2] = cnt;
            }
        }
    }
    for (int i = 1; i <= n-2; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
        {
            if(a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W')
            {
                cnt ++;
                type[cnt] = 2;
                //g.push_back(tri(i, j, 1, cnt));
                dir1[i][j] = cnt;
                dir1[i+1][j] = cnt;
                dir1[i+2][j] = cnt;
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
        {
            if(dir0[i][j] && dir1[i][j])
            {
                v[dir0[i][j]].push_back(dir1[i][j]);
                v[dir1[i][j]].push_back(dir0[i][j]);
            }
        }
    }
}
int used[MAXN];
int cnt1 = 0, cnt2 = 0;
void dfs(int beg)
{
    used[beg] = 1;
    if(type[beg] == 1)cnt1 ++;
    else cnt2 ++;
    int nb;
    for (int i = 0; i < v[beg].size(); ++ i)
    {
        nb = v[beg][i];
        if(!used[nb])dfs(nb);
    }
}
void solve()
{
    int ans = 0;
    for (int i = 1; i <= cnt; ++ i)
    {
        if(!used[i])
        {
            cnt1 = 0;
            cnt2 = 0;
            dfs(i);
            ans += max(cnt1, cnt2);
        }
    }
    cout << ans << endl;
}
int main()
{
    speed();

    read();
    precompute();
    solve();
    return 0;
}

Compilation message

dango_maker.cpp: In function 'void dfs(int)':
dango_maker.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < v[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 211592 KB Output is correct
2 Correct 88 ms 211596 KB Output is correct
3 Correct 87 ms 211648 KB Output is correct
4 Correct 87 ms 211564 KB Output is correct
5 Correct 90 ms 211596 KB Output is correct
6 Correct 89 ms 211588 KB Output is correct
7 Correct 94 ms 211792 KB Output is correct
8 Correct 89 ms 211656 KB Output is correct
9 Correct 88 ms 211616 KB Output is correct
10 Correct 86 ms 211592 KB Output is correct
11 Correct 87 ms 211600 KB Output is correct
12 Correct 87 ms 211672 KB Output is correct
13 Correct 85 ms 211712 KB Output is correct
14 Correct 88 ms 211692 KB Output is correct
15 Correct 88 ms 211612 KB Output is correct
16 Correct 88 ms 211700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 211592 KB Output is correct
2 Correct 88 ms 211596 KB Output is correct
3 Correct 87 ms 211648 KB Output is correct
4 Correct 87 ms 211564 KB Output is correct
5 Correct 90 ms 211596 KB Output is correct
6 Correct 89 ms 211588 KB Output is correct
7 Correct 94 ms 211792 KB Output is correct
8 Correct 89 ms 211656 KB Output is correct
9 Correct 88 ms 211616 KB Output is correct
10 Correct 86 ms 211592 KB Output is correct
11 Correct 87 ms 211600 KB Output is correct
12 Correct 87 ms 211672 KB Output is correct
13 Correct 85 ms 211712 KB Output is correct
14 Correct 88 ms 211692 KB Output is correct
15 Correct 88 ms 211612 KB Output is correct
16 Correct 88 ms 211700 KB Output is correct
17 Correct 87 ms 211672 KB Output is correct
18 Correct 98 ms 211708 KB Output is correct
19 Correct 86 ms 211656 KB Output is correct
20 Correct 86 ms 211668 KB Output is correct
21 Correct 87 ms 211656 KB Output is correct
22 Correct 89 ms 211736 KB Output is correct
23 Correct 87 ms 211620 KB Output is correct
24 Correct 87 ms 211620 KB Output is correct
25 Correct 90 ms 211588 KB Output is correct
26 Correct 87 ms 211660 KB Output is correct
27 Correct 88 ms 211780 KB Output is correct
28 Correct 92 ms 211736 KB Output is correct
29 Correct 91 ms 211736 KB Output is correct
30 Correct 89 ms 211648 KB Output is correct
31 Correct 89 ms 211680 KB Output is correct
32 Correct 88 ms 211624 KB Output is correct
33 Correct 91 ms 211788 KB Output is correct
34 Incorrect 88 ms 211788 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 211592 KB Output is correct
2 Correct 88 ms 211596 KB Output is correct
3 Correct 87 ms 211648 KB Output is correct
4 Correct 87 ms 211564 KB Output is correct
5 Correct 90 ms 211596 KB Output is correct
6 Correct 89 ms 211588 KB Output is correct
7 Correct 94 ms 211792 KB Output is correct
8 Correct 89 ms 211656 KB Output is correct
9 Correct 88 ms 211616 KB Output is correct
10 Correct 86 ms 211592 KB Output is correct
11 Correct 87 ms 211600 KB Output is correct
12 Correct 87 ms 211672 KB Output is correct
13 Correct 85 ms 211712 KB Output is correct
14 Correct 88 ms 211692 KB Output is correct
15 Correct 88 ms 211612 KB Output is correct
16 Correct 88 ms 211700 KB Output is correct
17 Correct 87 ms 211672 KB Output is correct
18 Correct 98 ms 211708 KB Output is correct
19 Correct 86 ms 211656 KB Output is correct
20 Correct 86 ms 211668 KB Output is correct
21 Correct 87 ms 211656 KB Output is correct
22 Correct 89 ms 211736 KB Output is correct
23 Correct 87 ms 211620 KB Output is correct
24 Correct 87 ms 211620 KB Output is correct
25 Correct 90 ms 211588 KB Output is correct
26 Correct 87 ms 211660 KB Output is correct
27 Correct 88 ms 211780 KB Output is correct
28 Correct 92 ms 211736 KB Output is correct
29 Correct 91 ms 211736 KB Output is correct
30 Correct 89 ms 211648 KB Output is correct
31 Correct 89 ms 211680 KB Output is correct
32 Correct 88 ms 211624 KB Output is correct
33 Correct 91 ms 211788 KB Output is correct
34 Incorrect 88 ms 211788 KB Output isn't correct
35 Halted 0 ms 0 KB -