oj.uz

Submission #366810

# Submission time Handle Problem Language Result Execution time Memory
366810 2021-02-15T10:17:25 Z ngpin04 Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 561 ms 47480 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 4e3 + 5;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

char a[N][N];

int n,m,ans;

bool vis[N][N];

void bfs(int i, int j)
{
    queue <pair <int, int>> q;

    q.push(mp(i, j));
    vis[i][j] = true;

    while (q.size())
    {
        pair <int, int> cur = q.front();
        q.pop();
        int x = cur.fi;
        int y = cur.se;

        for (int dir = 0; dir < 4; dir++)
        {
            int u = x + dx[dir];
            int v = y + dy[dir];
            if (a[u][v] == a[i][j] && min(u, v) > 0 && u <= n && v <= m && !vis[u][v])
            {
                vis[u][v] = true;
                q.push(mp(u, v));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j - 1];
    }

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) if (!vis[i][j] && a[i][j] == a[n][m])
    {
        bfs(i, j);
        ans++;
    }

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] != a[n][m])
            return cout << ans + 1, 0;

    cout << ans;
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 4460 KB Output isn't correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Incorrect 1 ms 748 KB Output isn't correct
4 Incorrect 7 ms 4332 KB Output isn't correct
5 Incorrect 3 ms 2668 KB Output isn't correct
6 Incorrect 1 ms 492 KB Output isn't correct
7 Incorrect 1 ms 876 KB Output isn't correct
8 Incorrect 1 ms 876 KB Output isn't correct
9 Incorrect 1 ms 1132 KB Output isn't correct
10 Incorrect 3 ms 2412 KB Output isn't correct
11 Incorrect 3 ms 1900 KB Output isn't correct
12 Incorrect 5 ms 2668 KB Output isn't correct
13 Incorrect 3 ms 2668 KB Output isn't correct
14 Incorrect 3 ms 2668 KB Output isn't correct
15 Incorrect 10 ms 4588 KB Output isn't correct
16 Incorrect 11 ms 4460 KB Output isn't correct
17 Incorrect 7 ms 4332 KB Output isn't correct
18 Incorrect 8 ms 4332 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 30316 KB Output isn't correct
2 Incorrect 32 ms 11756 KB Output isn't correct
3 Incorrect 180 ms 47348 KB Output isn't correct
4 Incorrect 42 ms 18796 KB Output isn't correct
5 Incorrect 196 ms 32748 KB Output isn't correct
6 Incorrect 416 ms 47340 KB Output isn't correct
7 Incorrect 21 ms 31724 KB Output isn't correct
8 Incorrect 21 ms 30316 KB Output isn't correct
9 Incorrect 2 ms 492 KB Output isn't correct
10 Incorrect 1 ms 512 KB Output isn't correct
11 Incorrect 22 ms 31212 KB Output isn't correct
12 Incorrect 2 ms 1516 KB Output isn't correct
13 Incorrect 38 ms 11756 KB Output isn't correct
14 Incorrect 25 ms 8428 KB Output isn't correct
15 Incorrect 19 ms 9196 KB Output isn't correct
16 Incorrect 15 ms 4204 KB Output isn't correct
17 Incorrect 73 ms 20204 KB Output isn't correct
18 Incorrect 59 ms 20076 KB Output isn't correct
19 Incorrect 41 ms 18796 KB Output isn't correct
20 Incorrect 59 ms 17516 KB Output isn't correct
21 Incorrect 109 ms 33772 KB Output isn't correct
22 Incorrect 197 ms 32876 KB Output isn't correct
23 Incorrect 131 ms 27500 KB Output isn't correct
24 Incorrect 133 ms 33900 KB Output isn't correct
25 Incorrect 214 ms 47320 KB Output isn't correct
26 Correct 561 ms 39916 KB Output is correct
27 Incorrect 537 ms 47468 KB Output isn't correct
28 Incorrect 421 ms 47480 KB Output isn't correct
29 Incorrect 409 ms 47340 KB Output isn't correct
30 Incorrect 316 ms 46444 KB Output isn't correct
31 Incorrect 358 ms 35692 KB Output isn't correct
32 Incorrect 108 ms 47436 KB Output isn't correct