oj.uz

Submission #1040788

# Submission time Handle Problem Language Result Execution time Memory
1040788 2024-08-01T09:21:30 Z GuessWhoHas2Cats Tracks in the Snow (BOI13_tracks) C++14
75.3125 / 100
 377 ms 125956 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, INT_MAX));
    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] != INT_MAX)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 1884 KB Output isn't correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 604 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 824 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 1880 KB Output is correct
16 Incorrect 6 ms 1972 KB Output isn't correct
17 Correct 4 ms 1628 KB Output is correct
18 Correct 3 ms 1884 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 57716 KB Output is correct
2 Correct 22 ms 9820 KB Output is correct
3 Correct 115 ms 96636 KB Output is correct
4 Incorrect 38 ms 22364 KB Output isn't correct
5 Correct 81 ms 54360 KB Output is correct
6 Correct 377 ms 111316 KB Output is correct
7 Correct 20 ms 63260 KB Output is correct
8 Correct 18 ms 57720 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Correct 19 ms 60964 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 22 ms 9832 KB Output is correct
14 Incorrect 12 ms 5620 KB Output isn't correct
15 Correct 8 ms 6236 KB Output is correct
16 Incorrect 2 ms 2396 KB Output isn't correct
17 Correct 54 ms 24652 KB Output is correct
18 Correct 36 ms 24376 KB Output is correct
19 Incorrect 31 ms 22064 KB Output isn't correct
20 Incorrect 10 ms 20060 KB Output isn't correct
21 Correct 68 ms 57216 KB Output is correct
22 Correct 82 ms 54352 KB Output is correct
23 Incorrect 84 ms 41044 KB Output isn't correct
24 Correct 74 ms 57088 KB Output is correct
25 Correct 160 ms 96436 KB Output is correct
26 Correct 182 ms 123996 KB Output is correct
27 Correct 275 ms 125956 KB Output is correct
28 Correct 368 ms 111136 KB Output is correct
29 Correct 363 ms 107124 KB Output is correct
30 Correct 313 ms 113112 KB Output is correct
31 Incorrect 303 ms 62036 KB Output isn't correct
32 Correct 248 ms 116092 KB Output is correct