oj.uz

Submission #1101438

# Submission time Handle Problem Language Result Execution time Memory
1101438 2024-10-16T08:28:55 Z abel2008 Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 1048580 KB 
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
int n,m,cnt = 0,di[4] = {-1,0,1,0},dj[4] = {0,1,0,-1},maxx = 0;
bool adj[4003][4003];
bool viz[4003][4003];
int viz1[4003*4003];
char ma[4003][4003];

bool inside(int x,int y) {
        return x>=1&&x<=n&&y>=1&&y<=m;
}

void dfs(int x,int y,int crt,char ch) {
        viz[x][y] = crt;
        for (int k = 0;k<4;++k) {
                int crtx = x+di[k],crty = y+dj[k];
                if (inside(crtx,crty)&&viz[crtx][crty]==0&&ma[crtx][crty]==ch) {
                        dfs(crtx,crty,crt,ch);
                } else if (inside(crtx,crty)&&viz[crtx][crty]!=0&&ma[crtx][crty]!=ch) {
                        adj[crt][viz[crtx][crty]] = 1;
                        adj[viz[crtx][crty]][crt] = 1;
                }
        }
}

void bfs(int k) {
        viz1[k] = 1;
        queue<int> Q;
        Q.push(k);
        maxx = max(maxx,viz1[k]);
        while(!Q.empty()) {
                int crt = Q.front();
                Q.pop();
                for (int j = 1;j<=m;++j) {
                        if (adj[k][j]) {
                                if (viz1[j]==0) {
                                        viz1[j] = viz1[crt]+1;
                                        Q.push(crt);
                                        maxx = max(maxx,viz1[j]);
                                }
                        }
                }
        }
}


int main() {
        cin>>n>>m;
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=m;++j) {
                        cin>>ma[i][j];
                }
        }
        for (int i = 1;i<=n;++i) {
                for (int j = 1;j<=m;++j) {
                        if (ma[i][j]!='.'&&viz[i][j]==0) {
                                dfs(i,j,++cnt,ma[i][j]);
                        }
                }
        }
        bfs(1);
        cout<<maxx<<endl;
        return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 44096 KB Execution killed with signal 11
2 Incorrect 2 ms 6912 KB Output isn't correct
3 Incorrect 2 ms 9208 KB Output isn't correct
4 Incorrect 12 ms 22380 KB Output isn't correct
5 Runtime error 47 ms 42232 KB Execution killed with signal 11
6 Incorrect 1 ms 6908 KB Output isn't correct
7 Incorrect 2 ms 9040 KB Output isn't correct
8 Incorrect 2 ms 9040 KB Output isn't correct
9 Incorrect 2 ms 9040 KB Output isn't correct
10 Runtime error 36 ms 42056 KB Execution killed with signal 11
11 Incorrect 5 ms 12368 KB Output isn't correct
12 Runtime error 38 ms 42388 KB Execution killed with signal 11
13 Runtime error 51 ms 42312 KB Execution killed with signal 11
14 Runtime error 46 ms 42312 KB Execution killed with signal 11
15 Runtime error 52 ms 44012 KB Execution killed with signal 11
16 Runtime error 46 ms 43996 KB Execution killed with signal 11
17 Runtime error 56 ms 43884 KB Execution killed with signal 11
18 Incorrect 12 ms 22604 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 96812 KB Execution killed with signal 11
2 Runtime error 122 ms 58720 KB Execution killed with signal 11
3 Runtime error 551 ms 99172 KB Execution killed with signal 11
4 Runtime error 225 ms 67912 KB Execution killed with signal 11
5 Runtime error 326 ms 85608 KB Execution killed with signal 11
6 Runtime error 891 ms 299112 KB Execution killed with signal 11
7 Runtime error 94 ms 98120 KB Execution killed with signal 11
8 Runtime error 109 ms 96584 KB Execution killed with signal 11
9 Runtime error 31 ms 36352 KB Execution killed with signal 11
10 Incorrect 14 ms 15360 KB Output isn't correct
11 Incorrect 14 ms 41448 KB Output isn't correct
12 Runtime error 35 ms 41156 KB Execution killed with signal 11
13 Runtime error 89 ms 58696 KB Execution killed with signal 11
14 Runtime error 64 ms 51556 KB Execution killed with signal 11
15 Runtime error 66 ms 52308 KB Execution killed with signal 11
16 Runtime error 50 ms 43568 KB Execution killed with signal 11
17 Runtime error 167 ms 69224 KB Execution killed with signal 11
18 Runtime error 158 ms 68976 KB Execution killed with signal 11
19 Runtime error 151 ms 67944 KB Execution killed with signal 11
20 Runtime error 142 ms 66916 KB Execution killed with signal 11
21 Runtime error 342 ms 86344 KB Execution killed with signal 11
22 Runtime error 336 ms 85576 KB Execution killed with signal 11
23 Runtime error 287 ms 77640 KB Execution killed with signal 11
24 Runtime error 323 ms 86608 KB Execution killed with signal 11
25 Runtime error 511 ms 98632 KB Execution killed with signal 11
26 Runtime error 1389 ms 1048576 KB Execution killed with signal 9
27 Execution timed out 2569 ms 1048576 KB Time limit exceeded
28 Runtime error 830 ms 299112 KB Execution killed with signal 11
29 Runtime error 911 ms 318572 KB Execution killed with signal 11
30 Runtime error 821 ms 310844 KB Execution killed with signal 11
31 Runtime error 355 ms 91980 KB Execution killed with signal 11
32 Execution timed out 2735 ms 1048580 KB Time limit exceeded