oj.uz

답안 #148263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148263 2019-08-31T19:11:30 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[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;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 395 ms 387144 KB Output is correct
2 Correct 343 ms 376304 KB Output is correct
3 Correct 344 ms 376492 KB Output is correct
4 Correct 376 ms 385464 KB Output is correct
5 Correct 348 ms 379260 KB Output is correct
6 Correct 340 ms 376204 KB Output is correct
7 Correct 339 ms 376524 KB Output is correct
8 Correct 352 ms 376764 KB Output is correct
9 Correct 352 ms 376916 KB Output is correct
10 Correct 357 ms 378808 KB Output is correct
11 Correct 357 ms 379332 KB Output is correct
12 Correct 371 ms 380956 KB Output is correct
13 Correct 360 ms 379256 KB Output is correct
14 Correct 350 ms 379256 KB Output is correct
15 Correct 394 ms 385584 KB Output is correct
16 Correct 398 ms 387228 KB Output is correct
17 Correct 379 ms 383432 KB Output is correct
18 Correct 367 ms 385444 KB Output is correct

Subtask #2
52.5 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 407256 KB Output is correct
2 Correct 504 ms 406280 KB Output is correct
3 Correct 1275 ms 535588 KB Output is correct
4 Correct 563 ms 421032 KB Output is correct
5 Correct 1253 ms 587604 KB Output is correct
6 Execution timed out 2135 ms 845188 KB Time limit exceeded
7 Correct 379 ms 408780 KB Output is correct
8 Correct 380 ms 407216 KB Output is correct
9 Correct 351 ms 377352 KB Output is correct
10 Correct 347 ms 376520 KB Output is correct
11 Correct 379 ms 407780 KB Output is correct
12 Correct 346 ms 377756 KB Output is correct
13 Correct 500 ms 406368 KB Output is correct
14 Correct 435 ms 395304 KB Output is correct
15 Correct 428 ms 394940 KB Output is correct
16 Correct 419 ms 390140 KB Output is correct
17 Correct 748 ms 443484 KB Output is correct
18 Correct 671 ms 434728 KB Output is correct
19 Correct 558 ms 421100 KB Output is correct
20 Correct 568 ms 421548 KB Output is correct
21 Correct 911 ms 480024 KB Output is correct
22 Correct 1256 ms 587596 KB Output is correct
23 Correct 1099 ms 496036 KB Output is correct
24 Correct 940 ms 487740 KB Output is correct
25 Correct 1831 ms 561840 KB Output is correct
26 Runtime error 1361 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Execution timed out 2133 ms 1028708 KB Time limit exceeded
28 Execution timed out 2075 ms 825712 KB Time limit exceeded
29 Execution timed out 2103 ms 814436 KB Time limit exceeded
30 Execution timed out 2079 ms 884812 KB Time limit exceeded
31 Execution timed out 2069 ms 710200 KB Time limit exceeded
32 Execution timed out 2151 ms 968840 KB Time limit exceeded