oj.uz

Submission #148264

# Submission time Handle Problem Language Result Execution time Memory
148264 2019-08-31T19:14:37 Z dolphingarlic Tracks in the Snow (BOI13_tracks) C++14
82.5 / 100
 2000 ms 1048580 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#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[8000050];
int visited[8000050], q[8000050];

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);
        }
    }

    int rp = -1, lp = 0;
    q[++rp] = 1;
    visited[1] = 1;
    while (rp >= lp) {
        int curr = q[lp++];

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

    cout << ans;
    return 0;
}

Compilation message

tracks.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 199384 KB Output is correct
2 Correct 175 ms 188428 KB Output is correct
3 Correct 175 ms 188624 KB Output is correct
4 Correct 198 ms 197448 KB Output is correct
5 Correct 182 ms 191352 KB Output is correct
6 Correct 177 ms 188396 KB Output is correct
7 Correct 177 ms 188616 KB Output is correct
8 Correct 176 ms 188924 KB Output is correct
9 Correct 176 ms 189148 KB Output is correct
10 Correct 181 ms 191052 KB Output is correct
11 Correct 189 ms 191388 KB Output is correct
12 Correct 191 ms 193164 KB Output is correct
13 Correct 181 ms 191368 KB Output is correct
14 Correct 183 ms 191416 KB Output is correct
15 Correct 215 ms 197836 KB Output is correct
16 Correct 220 ms 199344 KB Output is correct
17 Correct 207 ms 195768 KB Output is correct
18 Correct 206 ms 197444 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 219168 KB Output is correct
2 Correct 333 ms 219224 KB Output is correct
3 Correct 1116 ms 346420 KB Output is correct
4 Correct 388 ms 234248 KB Output is correct
5 Correct 1042 ms 417332 KB Output is correct
6 Execution timed out 2141 ms 706336 KB Time limit exceeded
7 Correct 209 ms 220504 KB Output is correct
8 Correct 208 ms 219164 KB Output is correct
9 Correct 186 ms 189444 KB Output is correct
10 Correct 178 ms 188780 KB Output is correct
11 Correct 209 ms 219768 KB Output is correct
12 Correct 178 ms 190008 KB Output is correct
13 Correct 332 ms 219252 KB Output is correct
14 Correct 269 ms 207916 KB Output is correct
15 Correct 259 ms 207632 KB Output is correct
16 Correct 259 ms 202540 KB Output is correct
17 Correct 583 ms 257500 KB Output is correct
18 Correct 510 ms 248656 KB Output is correct
19 Correct 389 ms 234156 KB Output is correct
20 Correct 394 ms 235088 KB Output is correct
21 Correct 732 ms 295564 KB Output is correct
22 Correct 1085 ms 417396 KB Output is correct
23 Correct 937 ms 312008 KB Output is correct
24 Correct 756 ms 305824 KB Output is correct
25 Correct 1703 ms 385720 KB Output is correct
26 Runtime error 1472 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Execution timed out 2100 ms 863756 KB Time limit exceeded
28 Execution timed out 2050 ms 690088 KB Time limit exceeded
29 Execution timed out 2062 ms 682060 KB Time limit exceeded
30 Execution timed out 2124 ms 696900 KB Time limit exceeded
31 Execution timed out 2073 ms 527932 KB Time limit exceeded
32 Execution timed out 2092 ms 821708 KB Time limit exceeded