oj.uz

답안 #1102487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102487 2024-10-18T07:59:59 Z qrn Zoo (COCI19_zoo) C++14
110 / 110
 384 ms 138312 KB 
#include <bits/stdc++.h>
using namespace std;

template<class ISqr, class T>
ISqr& operator>>(ISqr& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define fi first
#define se second
 
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define ll long long

vector<vector<vector<int>>> v;
int bfs(int n, int st){
    vector<int> di(n, 1000000000);
    deque<int> q;
    di[st] = 0;
    q.push_back(st);
    while (!q.empty()){
        int x = q.front();
        q.pop_front();
        for (auto el : v[x]){
            if (di[el[0]] > di[x] + el[1]){
                di[el[0]] = di[x] + el[1];
                if (el[1] == 0){
                    q.push_front(el[0]);
                }
                else{
                    q.push_back(el[0]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (di[i] == 1000000000) continue;
        ans = max(ans, di[i]);
    }
    return ans;
}
int main(){
    int n, m;
    cin>>n>>m;
    map<char, int> ma;
    ma['B'] = 0;
    ma['T'] = 1;
    v.resize(n * m);
    vector<string> s(n);
    for (int i = 0; i < n; i++){
        cin>>s[i];
        for (int j = 0; j < m; j++){
            if (s[i][j] == '*') continue;
            int v1 = i * m + j;
            if (i != 0 && s[i - 1][j] != '*'){
                int v2 = (i - 1) * m + j;
                v[v1].push_back({v2, ma[s[i][j]] ^ ma[s[i - 1][j]]});
                v[v2].push_back({v1, ma[s[i][j]] ^ ma[s[i - 1][j]]});
            }
            if (j != 0 && s[i][j - 1] != '*'){
                int v2 = i * m + j - 1;
                v[v1].push_back({v2, ma[s[i][j]] ^ ma[s[i][j - 1]]});
                v[v2].push_back({v1, ma[s[i][j]] ^ ma[s[i][j - 1]]});
            }
        }
    }
    cout << bfs(n * m, 0) + 1 << endl;
}

Subtask #1
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 1616 KB Output is correct
7 Correct 4 ms 1616 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1360 KB Output is correct
10 Correct 4 ms 1616 KB Output is correct
11 Correct 3 ms 1360 KB Output is correct
12 Correct 4 ms 1688 KB Output is correct
13 Correct 4 ms 1360 KB Output is correct
14 Correct 5 ms 1360 KB Output is correct
15 Correct 3 ms 1360 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 1616 KB Output is correct
7 Correct 4 ms 1616 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1360 KB Output is correct
10 Correct 4 ms 1616 KB Output is correct
11 Correct 3 ms 1360 KB Output is correct
12 Correct 4 ms 1688 KB Output is correct
13 Correct 4 ms 1360 KB Output is correct
14 Correct 5 ms 1360 KB Output is correct
15 Correct 3 ms 1360 KB Output is correct
16 Correct 69 ms 43428 KB Output is correct
17 Correct 71 ms 44628 KB Output is correct
18 Correct 61 ms 44628 KB Output is correct
19 Correct 83 ms 51012 KB Output is correct
20 Correct 63 ms 44368 KB Output is correct
21 Correct 350 ms 130888 KB Output is correct
22 Correct 328 ms 131144 KB Output is correct
23 Correct 345 ms 132424 KB Output is correct
24 Correct 332 ms 138312 KB Output is correct
25 Correct 349 ms 135456 KB Output is correct
26 Correct 328 ms 134472 KB Output is correct
27 Correct 347 ms 130204 KB Output is correct
28 Correct 323 ms 129324 KB Output is correct
29 Correct 384 ms 136928 KB Output is correct
30 Correct 371 ms 135752 KB Output is correct