oj.uz

Submission #877966

# Submission time Handle Problem Language Result Execution time Memory
877966 2023-11-23T23:03:23 Z tigar Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

int w, h;
char snow[4001][4001];
int check[4001][4001];
map<pair<int, int>, bool>ch;
vector<int>graff[4040];
queue<int>q;
int ans=0;
bool checkk[4040];
int dist[4040];

void dfs(int x, int y, int br)
{
    if(check[x][y]!=0){return;}
    check[x][y]=br;
    int k;
    if(x-1>0)
    {
        if(snow[x-1][y]==snow[x][y])dfs(x-1, y, br);
        else if(snow[x-1][y]!='.')
        {
            if(!ch[{check[x-1][y], br}] and check[x-1][y]!=0)
            {
                ch[{check[x-1][y], br}]=true;
                graff[check[x-1][y]].push_back(br);
                graff[br].push_back(check[x-1][y]);
            }
        }
    }
    if(x+1<=h)
    {
        if(snow[x][y]==snow[x+1][y])dfs(x+1, y, br);
        else if(snow[x+1][y]!='.')
        {
            if(!ch[{check[x+1][y], br}] and check[x+1][y]!=0)
            {
                ch[{check[x+1][y], br}]=true;
                graff[check[x+1][y]].push_back(br);
                graff[br].push_back(check[x+1][y]);
            }
        }
    }
    if(y-1>0)
    {
        if(snow[x][y]==snow[x][y-1])dfs(x, y-1, br);
        else if(snow[x][y-1]!='.')
        {
            if(!ch[{check[x][y-1], br}] and check[x][y-1]!=0)
            {
                ch[{check[x][y-1], br}]=true;
                graff[check[x][y-1]].push_back(br);
                graff[br].push_back(check[x][y-1]);
            }
        }
    }
    if(y+1<=w)
    {
        if(snow[x][y]==snow[x][y+1])dfs(x, y+1, br);
        else if(snow[x][y+1]!='.')
        {
            if(!ch[{check[x][y+1], br}] and check[x][y+1]!=0)
            {
                ch[{check[x][y+1], br}]=true;
                graff[check[x][y+1]].push_back(br);
                graff[br].push_back(check[x][y+1]);
            }
        }
    }
    return;
}

void bfs(int v)
{
    if(q.empty())return;
    q.pop();
    for(int i=0; i<graff[v].size(); i++)
    {
        if(!checkk[graff[v][i]])
        {
            checkk[graff[v][i]]=true;
            q.push(graff[v][i]);
            dist[graff[v][i]]=dist[v]+1;
            ans=max(ans, dist[graff[v][i]]);
        }
    }
    int ad=q.front();
    bfs(ad);
    return;
}

int main()
{
    cin>>h>>w;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)cin>>snow[i][j];
    }
    int brr=1;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)
        {
            if(snow[i][j]=='.')check[i][j]=true;
            else if(!check[i][j]){dfs(i, j, brr); brr++;}
        }
    }
    q.push(1);
    bfs(1);
    cout<<ans;
    return 0;
}

Compilation message

tracks.cpp: In function 'void dfs(int, int, int)':
tracks.cpp:19:9: warning: unused variable 'k' [-Wunused-variable]
   19 |     int k;
      |         ^
tracks.cpp: In function 'void bfs(int)':
tracks.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0; i<graff[v].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 15660 KB Execution killed with signal 11
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Incorrect 15 ms 9052 KB Output isn't correct
5 Runtime error 16 ms 13172 KB Execution killed with signal 11
6 Incorrect 1 ms 2596 KB Output isn't correct
7 Incorrect 1 ms 2652 KB Output isn't correct
8 Incorrect 1 ms 2860 KB Output isn't correct
9 Incorrect 1 ms 2908 KB Output isn't correct
10 Runtime error 11 ms 8540 KB Execution killed with signal 11
11 Incorrect 4 ms 4440 KB Output isn't correct
12 Runtime error 17 ms 13304 KB Execution killed with signal 11
13 Runtime error 14 ms 13404 KB Execution killed with signal 11
14 Runtime error 14 ms 13180 KB Execution killed with signal 11
15 Runtime error 23 ms 15208 KB Execution killed with signal 11
16 Runtime error 24 ms 15240 KB Execution killed with signal 11
17 Runtime error 22 ms 14952 KB Execution killed with signal 11
18 Incorrect 14 ms 9264 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 67652 KB Execution killed with signal 11
2 Runtime error 72 ms 26904 KB Execution killed with signal 11
3 Runtime error 548 ms 85600 KB Execution killed with signal 11
4 Runtime error 151 ms 44936 KB Execution killed with signal 11
5 Runtime error 324 ms 65688 KB Execution killed with signal 11
6 Runtime error 825 ms 294680 KB Execution killed with signal 11
7 Runtime error 57 ms 69216 KB Execution killed with signal 11
8 Runtime error 60 ms 67628 KB Execution killed with signal 11
9 Runtime error 10 ms 7780 KB Execution killed with signal 11
10 Incorrect 3 ms 3420 KB Output isn't correct
11 Incorrect 11 ms 33640 KB Output isn't correct
12 Runtime error 8 ms 7516 KB Execution killed with signal 11
13 Runtime error 71 ms 27144 KB Execution killed with signal 11
14 Runtime error 54 ms 23560 KB Execution killed with signal 11
15 Runtime error 57 ms 24160 KB Execution killed with signal 11
16 Runtime error 43 ms 15028 KB Execution killed with signal 11
17 Runtime error 158 ms 44512 KB Execution killed with signal 11
18 Runtime error 160 ms 44172 KB Execution killed with signal 11
19 Runtime error 148 ms 44884 KB Execution killed with signal 11
20 Runtime error 156 ms 37388 KB Execution killed with signal 11
21 Runtime error 341 ms 67080 KB Execution killed with signal 11
22 Runtime error 365 ms 65688 KB Execution killed with signal 11
23 Runtime error 283 ms 56724 KB Execution killed with signal 11
24 Runtime error 348 ms 66912 KB Execution killed with signal 11
25 Runtime error 588 ms 85988 KB Execution killed with signal 11
26 Runtime error 1205 ms 1048576 KB Execution killed with signal 9
27 Execution timed out 3799 ms 1048576 KB Time limit exceeded
28 Runtime error 824 ms 294836 KB Execution killed with signal 11
29 Runtime error 876 ms 300172 KB Execution killed with signal 11
30 Runtime error 820 ms 256696 KB Execution killed with signal 11
31 Runtime error 371 ms 71008 KB Execution killed with signal 11
32 Execution timed out 4027 ms 1048576 KB Time limit exceeded