oj.uz

Submission #1101435

# Submission time Handle Problem Language Result Execution time Memory
1101435 2024-10-16T08:28:06 Z abel2008 Tracks in the Snow (BOI13_tracks) C++14
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 47 ms 44104 KB Execution killed with signal 11
2 Incorrect 1 ms 6904 KB Output isn't correct
3 Incorrect 2 ms 9040 KB Output isn't correct
4 Incorrect 13 ms 22608 KB Output isn't correct
5 Runtime error 35 ms 42360 KB Execution killed with signal 11
6 Incorrect 1 ms 6736 KB Output isn't correct
7 Incorrect 2 ms 9040 KB Output isn't correct
8 Incorrect 2 ms 9052 KB Output isn't correct
9 Incorrect 2 ms 9040 KB Output isn't correct
10 Runtime error 35 ms 41976 KB Execution killed with signal 11
11 Incorrect 5 ms 12368 KB Output isn't correct
12 Runtime error 39 ms 42400 KB Execution killed with signal 11
13 Runtime error 42 ms 42312 KB Execution killed with signal 11
14 Runtime error 38 ms 42312 KB Execution killed with signal 11
15 Runtime error 44 ms 44360 KB Execution killed with signal 11
16 Runtime error 44 ms 44360 KB Execution killed with signal 11
17 Runtime error 42 ms 44116 KB Execution killed with signal 11
18 Incorrect 15 ms 22608 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 84 ms 96840 KB Execution killed with signal 11
2 Runtime error 122 ms 60232 KB Execution killed with signal 11
3 Runtime error 553 ms 114908 KB Execution killed with signal 11
4 Runtime error 168 ms 71516 KB Execution killed with signal 11
5 Runtime error 360 ms 94536 KB Execution killed with signal 11
6 Runtime error 887 ms 314952 KB Execution killed with signal 11
7 Runtime error 83 ms 98060 KB Execution killed with signal 11
8 Runtime error 85 ms 96724 KB Execution killed with signal 11
9 Runtime error 35 ms 36680 KB Execution killed with signal 11
10 Incorrect 10 ms 15184 KB Output isn't correct
11 Incorrect 15 ms 41296 KB Output isn't correct
12 Runtime error 33 ms 41296 KB Execution killed with signal 11
13 Runtime error 91 ms 60232 KB Execution killed with signal 11
14 Runtime error 71 ms 52552 KB Execution killed with signal 11
15 Runtime error 70 ms 53320 KB Execution killed with signal 11
16 Runtime error 54 ms 43996 KB Execution killed with signal 11
17 Runtime error 170 ms 71356 KB Execution killed with signal 11
18 Runtime error 172 ms 71240 KB Execution killed with signal 11
19 Runtime error 163 ms 71512 KB Execution killed with signal 11
20 Runtime error 172 ms 70472 KB Execution killed with signal 11
21 Runtime error 324 ms 95560 KB Execution killed with signal 11
22 Runtime error 304 ms 94428 KB Execution killed with signal 11
23 Runtime error 274 ms 85196 KB Execution killed with signal 11
24 Runtime error 318 ms 95560 KB Execution killed with signal 11
25 Runtime error 507 ms 106824 KB Execution killed with signal 11
26 Runtime error 1299 ms 1048576 KB Execution killed with signal 9
27 Execution timed out 2611 ms 1048580 KB Time limit exceeded
28 Runtime error 847 ms 314852 KB Execution killed with signal 11
29 Runtime error 887 ms 334040 KB Execution killed with signal 11
30 Runtime error 863 ms 326120 KB Execution killed with signal 11
31 Runtime error 401 ms 101960 KB Execution killed with signal 11
32 Execution timed out 2857 ms 1048580 KB Time limit exceeded