oj.uz

Submission #44865

# Submission time Handle Problem Language Result Execution time Memory
44865 2018-04-08T19:45:19 Z iletavcioski Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 2000 ms 1048576 KB 
#include <iostream>
#include <queue>
using namespace std;
struct node 
{
    int x;
    int y;
};
int n,m;
char mat[4004][4004];
bool vis[4004][4004];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int brojac;
void bfs(queue<node> q1,queue<node> q2,int broj)
{
    if(q1.empty())
        return;
    brojac=broj;
    while(!q1.empty())
    {
        node g=q1.front();
        q1.pop();
        for(int i=0;i<4;i++)
        {
            if(g.x+dx[i]<n&&g.x+dx[i]>=0&&g.y+dy[i]<m&&g.y+dy[i]>=0)
            {
                if(!vis[g.x+dx[i]][g.y+dy[i]]&&mat[g.x+dx[i]][g.y+dy[i]]!='.')
                {
                    if(mat[g.x+dx[i]][g.y+dy[i]]!=mat[g.x][g.y])
                    {
                        node g1;
                        g1.x=g.x+dx[i];
                        g1.y=g.y+dy[i];
                        q2.push(g1);
                        vis[g1.x][g1.y]=true;
                    }
                    else
                    {
                        node g1;
                        g1.x=g.x+dx[i];
                        g1.y=g.y+dy[i];
                        q1.push(g1);
                        vis[g1.x][g1.y]=true;
                    }
                }
            }
        }
    }
    bfs(q2,q1,broj+1);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cin>>mat[i][j];
    }
    queue<node> q1,q2;
    node g;
    g.x=0;
    g.y=0;
    q1.push(g);
    vis[0][0]=true;
    bfs(q1,q2,1);
    cout<<brojac<<endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5496 KB Output is correct
2 Correct 3 ms 5496 KB Output is correct
3 Correct 2 ms 5496 KB Output is correct
4 Correct 14 ms 5496 KB Output is correct
5 Correct 8 ms 5496 KB Output is correct
6 Correct 2 ms 5496 KB Output is correct
7 Correct 2 ms 5496 KB Output is correct
8 Correct 3 ms 5496 KB Output is correct
9 Correct 3 ms 5496 KB Output is correct
10 Correct 7 ms 5496 KB Output is correct
11 Correct 7 ms 5496 KB Output is correct
12 Correct 9 ms 5496 KB Output is correct
13 Correct 6 ms 5496 KB Output is correct
14 Correct 6 ms 5496 KB Output is correct
15 Correct 20 ms 6536 KB Output is correct
16 Correct 22 ms 7048 KB Output is correct
17 Correct 17 ms 7048 KB Output is correct
18 Correct 13 ms 7048 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 39688 KB Output is correct
2 Correct 84 ms 39688 KB Output is correct
3 Correct 1261 ms 900812 KB Output is correct
4 Correct 133 ms 900812 KB Output is correct
5 Execution timed out 2105 ms 1048576 KB Time limit exceeded
6 Correct 1302 ms 1048576 KB Output is correct
7 Correct 33 ms 1048576 KB Output is correct
8 Correct 32 ms 1048576 KB Output is correct
9 Correct 4 ms 1048576 KB Output is correct
10 Correct 6 ms 1048576 KB Output is correct
11 Correct 28 ms 1048576 KB Output is correct
12 Correct 18 ms 1048576 KB Output is correct
13 Correct 83 ms 1048576 KB Output is correct
14 Correct 64 ms 1048576 KB Output is correct
15 Correct 257 ms 1048576 KB Output is correct
16 Correct 39 ms 1048576 KB Output is correct
17 Correct 227 ms 1048576 KB Output is correct
18 Correct 971 ms 1048576 KB Output is correct
19 Correct 139 ms 1048576 KB Output is correct
20 Correct 304 ms 1048576 KB Output is correct
21 Correct 811 ms 1048576 KB Output is correct
22 Execution timed out 2117 ms 1048576 KB Time limit exceeded
23 Correct 456 ms 1048576 KB Output is correct
24 Execution timed out 2103 ms 1048576 KB Time limit exceeded
25 Execution timed out 2153 ms 1048576 KB Time limit exceeded
26 Correct 754 ms 1048576 KB Output is correct
27 Correct 1000 ms 1048576 KB Output is correct
28 Correct 1160 ms 1048576 KB Output is correct
29 Correct 1120 ms 1048576 KB Output is correct
30 Correct 1072 ms 1048576 KB Output is correct
31 Correct 898 ms 1048576 KB Output is correct
32 Correct 863 ms 1048576 KB Output is correct