oj.uz

답안 #423509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423509 2021-06-11T08:20:39 Z blue Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1483 ms 103332 KB 
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
 
/*
Consider each connected component as one node in the graph.
Consider adjacent connected components as having an edge between them
Res = max distance between cc(1, 1) and any other cc
*/
 
int H, W;
 
int p(int i, int j)
{
    return (W+2)*i + j;
}
 
int main()
{
    cin >> H >> W;
 
    char c[(H+2)*(W+2)];
    for(int i = 0; i <= H; i++) c[p(i, 0)] = c[p(i, W+1)] = '.';
    for(int j = 0; j <= W; j++) c[p(0, j)] = c[p(H+1, j)] = '.';
    for(int i = 1; i <= H; i++)
    {
        for(int j = 1; j <= W; j++)
        {
            cin >> c[p(i, j)];
        }
    }
 
    int temp;
    vector<int> res((H+2)*(W+2), 1e9);
    res[p(1, 1)] = 0;
 
    deque<int> tbv;
    tbv.push_back(p(1, 1));
 
    int final_res = 0;
 
    while(!tbv.empty())
    {
        temp = tbv.front();
        tbv.pop_front();
        final_res = max(final_res, res[temp]);
 
        for(int k: {temp+1, temp-1, temp+W+2, temp-W-2})
        {
            if(c[k] == '.') continue;
            if(res[k] != 1e9) continue;
            if(c[temp] != c[k])
            {
                res[k] = res[temp] + 1;
                tbv.push_back(k);
            }
            else
            {
                res[k] = res[temp];
                tbv.push_front(k);
            }
        }
    }
 
    cout << final_res + 1 << '\n';
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1740 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 13 ms 1284 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 6 ms 688 KB Output is correct
11 Correct 4 ms 460 KB Output is correct
12 Correct 8 ms 820 KB Output is correct
13 Correct 8 ms 704 KB Output is correct
14 Correct 7 ms 800 KB Output is correct
15 Correct 22 ms 1668 KB Output is correct
16 Correct 24 ms 1652 KB Output is correct
17 Correct 20 ms 1648 KB Output is correct
18 Correct 13 ms 1228 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 121 ms 9484 KB Output is correct
3 Correct 1121 ms 94272 KB Output is correct
4 Correct 266 ms 22296 KB Output is correct
5 Correct 604 ms 53096 KB Output is correct
6 Correct 1392 ms 100932 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 4 ms 588 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 116 ms 9480 KB Output is correct
14 Correct 69 ms 5488 KB Output is correct
15 Correct 72 ms 6100 KB Output is correct
16 Correct 51 ms 3964 KB Output is correct
17 Correct 311 ms 24132 KB Output is correct
18 Correct 275 ms 23764 KB Output is correct
19 Correct 266 ms 22228 KB Output is correct
20 Correct 236 ms 20512 KB Output is correct
21 Correct 654 ms 54932 KB Output is correct
22 Correct 675 ms 53088 KB Output is correct
23 Correct 613 ms 45728 KB Output is correct
24 Correct 644 ms 53708 KB Output is correct
25 Correct 1316 ms 94264 KB Output is correct
26 Correct 1111 ms 97304 KB Output is correct
27 Correct 1353 ms 103332 KB Output is correct
28 Correct 1439 ms 100904 KB Output is correct
29 Correct 1400 ms 99736 KB Output is correct
30 Correct 1385 ms 100972 KB Output is correct
31 Correct 1002 ms 60592 KB Output is correct
32 Correct 1483 ms 102588 KB Output is correct