oj.uz

Submission #148260

# Submission time Handle Problem Language Result Execution time Memory
148260 2019-08-31T19:08:34 Z dolphingarlic Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 2000 ms 1048580 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, component[4000][4000], ans = 1;
char snow[4000][4000];

int num = 1;
vector<int> graph[16000050];
int visited[16000050];

void floodfill(int c, int x, int y) {
    component[x][y] = c;

    if (x > 0 && snow[x - 1][y] != '.') {
        if (snow[x - 1][y] == snow[x][y] && !component[x - 1][y]) floodfill(c, x - 1, y);
        else if (component[x - 1][y]) {
            graph[c].push_back(component[x - 1][y]);
            graph[component[x - 1][y]].push_back(c);
        }
    }
    if (x < n - 1 && snow[x + 1][y] != '.') {
        if (snow[x + 1][y] == snow[x][y] && !component[x + 1][y]) floodfill(c, x + 1, y);
        else if (component[x + 1][y]) {
            graph[c].push_back(component[x + 1][y]);
            graph[component[x + 1][y]].push_back(c);
        }
    }
    if (y > 0 && snow[x][y - 1] != '.') {
        if (snow[x][y - 1] == snow[x][y] && !component[x][y - 1]) floodfill(c, x, y - 1);
        else if (component[x][y - 1]) {
            graph[c].push_back(component[x][y - 1]);
            graph[component[x][y - 1]].push_back(c);
        }
    }
    if (y < m - 1 && snow[x][y + 1] != '.') {
        if (snow[x][y + 1] == snow[x][y] && !component[x][y + 1]) floodfill(c, x, y + 1);
        else if (component[x][y + 1]) {
            graph[c].push_back(component[x][y+ 1]);
            graph[component[x][y + 1]].push_back(c);
        }
    }
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    FOR(i, 0, n) FOR(j, 0, m) cin >> snow[i][j];

    FOR(i, 0, n) FOR(j, 0, m) {
        if (!component[i][j] && snow[i][j] != '.') {
            floodfill(num++, i, j);
        }
    }

    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int i : graph[curr]) {
            if (!visited[i]) {
                visited[i] = visited[curr] + 1;
                ans = max(ans, visited[i]);
                q.push(i);
            }
        }
    }

    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 387272 KB Output is correct
2 Correct 349 ms 376208 KB Output is correct
3 Correct 351 ms 376532 KB Output is correct
4 Correct 374 ms 385392 KB Output is correct
5 Correct 358 ms 379192 KB Output is correct
6 Correct 349 ms 376292 KB Output is correct
7 Correct 354 ms 376572 KB Output is correct
8 Correct 351 ms 376724 KB Output is correct
9 Correct 350 ms 376920 KB Output is correct
10 Correct 362 ms 378936 KB Output is correct
11 Correct 363 ms 379208 KB Output is correct
12 Correct 368 ms 380904 KB Output is correct
13 Correct 358 ms 379252 KB Output is correct
14 Correct 359 ms 379216 KB Output is correct
15 Correct 397 ms 385608 KB Output is correct
16 Correct 399 ms 387132 KB Output is correct
17 Correct 381 ms 383532 KB Output is correct
18 Correct 373 ms 385356 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 407156 KB Output is correct
2 Correct 518 ms 406336 KB Output is correct
3 Correct 1312 ms 530800 KB Output is correct
4 Correct 568 ms 421060 KB Output is correct
5 Correct 1282 ms 587568 KB Output is correct
6 Execution timed out 2079 ms 841336 KB Time limit exceeded
7 Correct 387 ms 408840 KB Output is correct
8 Correct 386 ms 407276 KB Output is correct
9 Correct 359 ms 377300 KB Output is correct
10 Correct 353 ms 376592 KB Output is correct
11 Correct 382 ms 407656 KB Output is correct
12 Correct 358 ms 377848 KB Output is correct
13 Correct 509 ms 406292 KB Output is correct
14 Correct 446 ms 395316 KB Output is correct
15 Correct 435 ms 394940 KB Output is correct
16 Correct 428 ms 390064 KB Output is correct
17 Correct 754 ms 443500 KB Output is correct
18 Correct 672 ms 434672 KB Output is correct
19 Correct 570 ms 421136 KB Output is correct
20 Correct 570 ms 421548 KB Output is correct
21 Correct 929 ms 480140 KB Output is correct
22 Correct 1293 ms 587632 KB Output is correct
23 Correct 1123 ms 496044 KB Output is correct
24 Correct 965 ms 487824 KB Output is correct
25 Correct 1894 ms 564728 KB Output is correct
26 Runtime error 1376 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Execution timed out 2144 ms 1028756 KB Time limit exceeded
28 Execution timed out 2098 ms 849500 KB Time limit exceeded
29 Execution timed out 2152 ms 849452 KB Time limit exceeded
30 Execution timed out 2138 ms 884864 KB Time limit exceeded
31 Execution timed out 2105 ms 710296 KB Time limit exceeded
32 Execution timed out 2141 ms 939128 KB Time limit exceeded