oj.uz

답안 #598728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598728 2022-07-18T20:37:29 Z stevancv Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1609 ms 717212 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 4e3 + 2;
int c[N][N], n, m, iden;
short a[N][N];
bool Can(int x, int y) {return 0 <= x && x < n && 0 <= y && y < m && c[x][y] == -1;}
void Dfs(int ii, int jj) {
    stack<pair<int, int>> st;
    st.push({ii, jj});
    while (!st.empty()) {
        int i = st.top().first;
        int j = st.top().second;
        st.pop();
        c[i][j] = iden;
        if (Can(i - 1, j) && a[i - 1][j] == a[i][j]) st.push({i - 1, j});
        if (Can(i, j - 1) && a[i][j - 1] == a[i][j]) st.push({i, j - 1});
        if (Can(i + 1, j) && a[i + 1][j] == a[i][j]) st.push({i + 1, j});
        if (Can(i, j + 1) && a[i][j + 1] == a[i][j]) st.push({i, j + 1});
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            c[i][j] = -1;
            if (s[j] == 'F') a[i][j] = 1;
            if (s[j] == 'R') a[i][j] = 2;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == -1 && a[i][j] > 0) {
                Dfs(i, j);
                iden += 1;
            }
        }
    }
    vector<set<int>> g(iden);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == -1) continue;
            if (i < n - 1 && c[i + 1][j] != c[i][j] && c[i + 1][j] != -1) {
                g[c[i][j]].insert(c[i + 1][j]);
                g[c[i + 1][j]].insert(c[i][j]);
            }
            if (j < m - 1 && c[i][j + 1] != c[i][j] && c[i][j + 1] != -1) {
                g[c[i][j]].insert(c[i][j + 1]);
                g[c[i][j + 1]].insert(c[i][j]);
            }
        }
    }
    vector<int> dist(iden, 1e9);
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int s = q.front(); q.pop();
        for (int u : g[s]) {
            if (dist[u] > dist[s] + 1) {
                dist[u] = dist[s] + 1;
                q.push(u);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < iden; i++) {
        smax(ans, dist[i] + 1);
    }
    cout << ans << en;
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 12492 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 15 ms 5596 KB Output is correct
5 Correct 6 ms 4308 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 5 ms 3924 KB Output is correct
11 Correct 4 ms 2260 KB Output is correct
12 Correct 13 ms 5608 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 29 ms 12116 KB Output is correct
16 Correct 41 ms 12480 KB Output is correct
17 Correct 24 ms 11500 KB Output is correct
18 Correct 12 ms 5588 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31916 KB Output is correct
2 Correct 118 ms 49992 KB Output is correct
3 Correct 569 ms 313640 KB Output is correct
4 Correct 164 ms 76120 KB Output is correct
5 Correct 913 ms 717088 KB Output is correct
6 Correct 1341 ms 175784 KB Output is correct
7 Correct 16 ms 33240 KB Output is correct
8 Correct 15 ms 31956 KB Output is correct
9 Correct 4 ms 1748 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 14 ms 32304 KB Output is correct
12 Correct 4 ms 3284 KB Output is correct
13 Correct 116 ms 50032 KB Output is correct
14 Correct 81 ms 30760 KB Output is correct
15 Correct 68 ms 34852 KB Output is correct
16 Correct 55 ms 21832 KB Output is correct
17 Correct 286 ms 119560 KB Output is correct
18 Correct 274 ms 119448 KB Output is correct
19 Correct 159 ms 76092 KB Output is correct
20 Correct 143 ms 82904 KB Output is correct
21 Correct 339 ms 203928 KB Output is correct
22 Correct 951 ms 717212 KB Output is correct
23 Correct 563 ms 217104 KB Output is correct
24 Correct 429 ms 283568 KB Output is correct
25 Correct 1128 ms 424172 KB Output is correct
26 Correct 546 ms 194864 KB Output is correct
27 Correct 735 ms 157352 KB Output is correct
28 Correct 1302 ms 175760 KB Output is correct
29 Correct 1187 ms 142276 KB Output is correct
30 Correct 1022 ms 126536 KB Output is correct
31 Correct 1609 ms 361040 KB Output is correct
32 Correct 673 ms 139504 KB Output is correct