oj.uz

Submission #511189

# Submission time Handle Problem Language Result Execution time Memory
511189 2022-01-15T11:19:00 Z DragosC1 Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 1048580 KB 
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
 
set<int> a[16000001];
char mat[4001][4001];
int comp[4001][4001];
bool viz[16000001];
queue<pair<int, int>> Q;
 
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
int n, m;
int l;
int Max;
 
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1}; 
 
bool inside(int i, int j) {
    if (i >= 1 && i <= n && j >= 1 && j <= m)
        return 1;
    return 0;
}
 
void dfs1(int i, int j) {
    int k, inou, jnou;
    comp[i][j] = l;
    for (k = 0; k < 4; k++) {
        inou = i + di[k], jnou = j + dj[k];
        if (inside(inou, jnou) && !comp[inou][jnou] && mat[inou][jnou] == mat[i][j])
            dfs1(inou, jnou);
    }
}
 
void dfs2(int i, int j) {
    int k, inou, jnou;
    viz[(i - 1) * m + j] = 1;
    for (k = 0; k < 4; k++) {
        inou = i + di[k], jnou = j + dj[k];
        if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] == mat[i][j])
            dfs2(inou, jnou);
        else if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] != '.') {
            a[comp[i][j]].insert(comp[inou][jnou]);
            a[comp[inou][jnou]].insert(comp[i][j]);
        }
    }
}
 
void bfs(int x) {
    int i;
    pair<int, int> p;
    Q.push({x, 1});
    viz[x] = 1;
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        if (p.second > Max)
            Max = p.second;
        for (int x : a[p.first]) {
            if (!viz[x]) {
                viz[x] = 1;
                Q.push({x, p.second + 1});
            }
        }   
    }
}
 
int main() {
    fast
    int i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> mat[i][j];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (!comp[i][j] && mat[i][j] != '.') {
                l++;
                dfs1(i, j);
            }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (!viz[(i - 1) * m + j] && mat[i][j] != '.') 
                dfs2(i, j);
    for (i = 1; i <= l; i++)
        viz[i] = 0;
    bfs(1);
    cout << Max;
    return 0;
}

Compilation message

tracks.cpp: In function 'void bfs(int)':
tracks.cpp:53:9: warning: unused variable 'i' [-Wunused-variable]
   53 |     int i;
      |         ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 762148 KB Output is correct
2 Correct 336 ms 751864 KB Output is correct
3 Correct 323 ms 752148 KB Output is correct
4 Correct 350 ms 758504 KB Output is correct
5 Correct 342 ms 755344 KB Output is correct
6 Correct 304 ms 751944 KB Output is correct
7 Correct 327 ms 752196 KB Output is correct
8 Correct 342 ms 752340 KB Output is correct
9 Correct 322 ms 752572 KB Output is correct
10 Correct 314 ms 754812 KB Output is correct
11 Correct 317 ms 754372 KB Output is correct
12 Correct 337 ms 756452 KB Output is correct
13 Correct 327 ms 755340 KB Output is correct
14 Correct 344 ms 755344 KB Output is correct
15 Correct 341 ms 761496 KB Output is correct
16 Correct 366 ms 762100 KB Output is correct
17 Correct 339 ms 761052 KB Output is correct
18 Correct 337 ms 758380 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 783136 KB Output is correct
2 Correct 451 ms 788680 KB Output is correct
3 Correct 1069 ms 974600 KB Output is correct
4 Correct 510 ms 810992 KB Output is correct
5 Runtime error 717 ms 1048580 KB Execution killed with signal 9
6 Correct 1957 ms 1000452 KB Output is correct
7 Correct 359 ms 784460 KB Output is correct
8 Correct 342 ms 783080 KB Output is correct
9 Correct 343 ms 753288 KB Output is correct
10 Correct 334 ms 752452 KB Output is correct
11 Correct 347 ms 783740 KB Output is correct
12 Correct 340 ms 754072 KB Output is correct
13 Correct 461 ms 788756 KB Output is correct
14 Correct 394 ms 774868 KB Output is correct
15 Correct 394 ms 778028 KB Output is correct
16 Correct 396 ms 767928 KB Output is correct
17 Correct 676 ms 837700 KB Output is correct
18 Correct 611 ms 839372 KB Output is correct
19 Correct 509 ms 810820 KB Output is correct
20 Correct 494 ms 811456 KB Output is correct
21 Correct 750 ms 893800 KB Output is correct
22 Runtime error 702 ms 1048580 KB Execution killed with signal 9
23 Correct 949 ms 905852 KB Output is correct
24 Correct 773 ms 942380 KB Output is correct
25 Runtime error 1002 ms 1048580 KB Execution killed with signal 9
26 Runtime error 602 ms 1048580 KB Execution killed with signal 9
27 Runtime error 656 ms 1048580 KB Execution killed with signal 9
28 Correct 1973 ms 1000268 KB Output is correct
29 Correct 1839 ms 986904 KB Output is correct
30 Runtime error 1372 ms 1048580 KB Execution killed with signal 9
31 Execution timed out 2128 ms 1041480 KB Time limit exceeded
32 Runtime error 631 ms 1048580 KB Execution killed with signal 9