oj.uz

Submission #1040791

# Submission time Handle Problem Language Result Execution time Memory
1040791 2024-08-01T09:24:20 Z GuessWhoHas2Cats Tracks in the Snow (BOI13_tracks) C++14
77.5 / 100
 374 ms 112288 KB 
#include<bits/stdc++.h>
#define a first
#define b second
using namespace std;
typedef pair<int, int>PII;
const int MAXL = 4000;
int n, m;
vector<string>graph;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
    int ans = 1; // 至少有一个animal
    iostream :: sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    graph.resize(n);
    for(int i = 0; i < n; i ++)
        cin >> graph[i];
    // 0-1 bfs 0 -> push_front, 1 -> push_back() --> increasing deque
    // q 存储位置
    // dist 存储到 start 的距离
    deque<PII>q;
    q.push_back({0, 0});
    vector<vector<int>>dist(n, vector<int>(n, 0));
    dist[0][0] = 1; // 根的depth是1
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();
        ans = max(ans, dist[t.a][t.b]);//已可用它更新其它点的dist是否最大

        // 字母走方向的图不是adj的图
        for(int i = 0; i < 4; i ++)
        {
            int x = t.a + dx[i], y = t.b + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m)continue;
            if((graph[x][y] == '.' ) || dist[x][y] != 0)continue;// un-visited
            // 在同一node内，weight为0
            if(graph[x][y] == graph[t.a][t.b])
            {
                q.push_front({x, y});
                dist[x][y] = dist[t.a][t.b];
            }
            else
            {
                q.push_back({x, y});
                dist[x][y] = dist[t.a][t.b] + 1;
            }

        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
25.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1624 KB Output isn't correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 1832 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 5 ms 1756 KB Output is correct
16 Incorrect 6 ms 1740 KB Output isn't correct
17 Correct 4 ms 1636 KB Output is correct
18 Correct 3 ms 1624 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 57688 KB Output is correct
2 Correct 21 ms 8284 KB Output is correct
3 Correct 108 ms 81028 KB Output is correct
4 Incorrect 32 ms 18520 KB Output isn't correct
5 Correct 81 ms 45456 KB Output is correct
6 Correct 371 ms 95684 KB Output is correct
7 Correct 20 ms 63316 KB Output is correct
8 Correct 18 ms 57692 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Correct 19 ms 60900 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 20 ms 8280 KB Output is correct
14 Incorrect 13 ms 4696 KB Output isn't correct
15 Correct 8 ms 5468 KB Output is correct
16 Incorrect 1 ms 1628 KB Output isn't correct
17 Correct 52 ms 20572 KB Output is correct
18 Correct 30 ms 20316 KB Output is correct
19 Incorrect 30 ms 18268 KB Output isn't correct
20 Incorrect 7 ms 16296 KB Output isn't correct
21 Correct 68 ms 48216 KB Output is correct
22 Correct 83 ms 45400 KB Output is correct
23 Incorrect 82 ms 33372 KB Output isn't correct
24 Correct 66 ms 48216 KB Output is correct
25 Correct 171 ms 80984 KB Output is correct
26 Correct 178 ms 112288 KB Output is correct
27 Correct 258 ms 110156 KB Output is correct
28 Correct 374 ms 95668 KB Output is correct
29 Correct 350 ms 91568 KB Output is correct
30 Correct 310 ms 98008 KB Output is correct
31 Correct 274 ms 52056 KB Output is correct
32 Correct 253 ms 100364 KB Output is correct