oj.uz

답안 #474824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474824 2021-09-20T01:45:17 Z dqk Tracks in the Snow (BOI13_tracks) C++17
10.4167 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> g(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> g[i];
    }
    std::vector<std::vector<int>> comp(n, std::vector<int>(m, 0));
    int num = 0;
    std::function<void(int, int, char)> dfs=[&](int x, int y, char c) {
        if (x < 0 || x >= n || y < 0 || y >= m || comp[x][y] || g[x][y] != c)
            return;
        comp[x][y] = num;
        dfs(x + 1, y, c);
        dfs(x - 1, y, c);
        dfs(x, y + 1, c);
        dfs(x, y - 1, c);
    };
    g.clear();
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < m; ++y) {
            if (comp[x][y] || g[x][y] == '.')
                continue;
            num++;
            dfs(x, y, g[x][y]);
        }
    }
    std::vector<std::vector<int>> adj(num + 1);
    auto addcomp=[&](int i, int j) {
        auto add=[&](int x, int y) {
            if (x < 0 || x >= n || y < 0 || y >= m)
                return;
            if (comp[x][y] && comp[x][y] != comp[i][j]) {
                adj[comp[x][y]].push_back(comp[i][j]);
                adj[comp[i][j]].push_back(comp[x][y]);
            }
        };
        add(i - 1, j);
        add(i + 1, j);
        add(i, j + 1);
        add(i, j - 1);
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (comp[i][j])
                addcomp(i, j); 
        }
    }
    comp.clear();
    std::vector<int> d(num + 1, 0);
    std::queue<int> q;
    q.push(1);
    d[1] = 1;
    int ans = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (d[v] == 0) {
                q.push(v);
                d[v] = d[u] + 1;
                ans = std::max(ans, d[v]);
            }
        }
    }
    std::cout << ans << "\n";
    return 0;
}

Subtask #1
1.66666666667 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 7620 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 14 ms 2888 KB Output isn't correct
5 Incorrect 6 ms 1228 KB Output isn't correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 6 ms 1356 KB Output isn't correct
11 Incorrect 5 ms 1024 KB Output isn't correct
12 Incorrect 16 ms 2840 KB Output isn't correct
13 Incorrect 6 ms 1284 KB Output isn't correct
14 Incorrect 6 ms 1260 KB Output isn't correct
15 Incorrect 36 ms 6248 KB Output isn't correct
16 Incorrect 46 ms 7492 KB Output isn't correct
17 Correct 26 ms 4292 KB Output is correct
18 Incorrect 14 ms 3000 KB Output isn't correct

Subtask #2
8.75 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1356 KB Output is correct
2 Incorrect 151 ms 24656 KB Output isn't correct
3 Incorrect 781 ms 168948 KB Output isn't correct
4 Incorrect 174 ms 31416 KB Output isn't correct
5 Incorrect 1106 ms 282500 KB Output isn't correct
6 Incorrect 1614 ms 218408 KB Output isn't correct
7 Correct 3 ms 1356 KB Output is correct
8 Correct 4 ms 1356 KB Output is correct
9 Incorrect 6 ms 1612 KB Output isn't correct
10 Incorrect 2 ms 844 KB Output isn't correct
11 Correct 2 ms 1228 KB Output is correct
12 Incorrect 3 ms 972 KB Output isn't correct
13 Incorrect 149 ms 24668 KB Output isn't correct
14 Incorrect 83 ms 14384 KB Output isn't correct
15 Incorrect 71 ms 12384 KB Output isn't correct
16 Incorrect 82 ms 12476 KB Output isn't correct
17 Incorrect 366 ms 61764 KB Output isn't correct
18 Incorrect 265 ms 46660 KB Output isn't correct
19 Incorrect 213 ms 31452 KB Output isn't correct
20 Incorrect 184 ms 38724 KB Output isn't correct
21 Incorrect 460 ms 99840 KB Output isn't correct
22 Incorrect 1090 ms 282452 KB Output isn't correct
23 Incorrect 720 ms 120028 KB Output isn't correct
24 Incorrect 606 ms 118804 KB Output isn't correct
25 Incorrect 1263 ms 188884 KB Output isn't correct
26 Runtime error 881 ms 1048576 KB Execution killed with signal 9
27 Incorrect 1258 ms 382440 KB Output isn't correct
28 Incorrect 1556 ms 218432 KB Output isn't correct
29 Incorrect 1449 ms 192824 KB Output isn't correct
30 Incorrect 1407 ms 237232 KB Output isn't correct
31 Execution timed out 2102 ms 308472 KB Time limit exceeded
32 Incorrect 1373 ms 359640 KB Output isn't correct