oj.uz

Submission #769870

# Submission time Handle Problem Language Result Execution time Memory
769870 2023-06-30T12:10:10 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
85.1042 / 100
 1598 ms 879224 KB 
#include <bits/stdc++.h>
using namespace std;
    
#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;
    
int H, W;
vector<string> grid;
    
vector<vector<ll>> visited; // bitset ?
    
//priority_queue<vector<ll>> q;
vector<vector<pair<ll, ll>>> pq_vec;
    
void dfs(int hat, int wat, ll num)
{
    //cerr << hat << " " << wat << " " <<num << "\n";
    //if (visited[hat][wat]>0) return;
    //if (grid[hat][wat] == '.') return;
    //visited[hat][wat] = num;
    
    char ch = grid[hat][wat];
    if (hat + 1 < H) {
        if (grid[hat + 1][wat] != '.' && visited[hat + 1][wat] < 0)
        {
            if (grid[hat + 1][wat] == ch) {
                pq_vec[num].push_back({hat + 1, wat});
                visited[hat][wat] = num;
            }
            else {
                pq_vec[num + 1].push_back({hat + 1, wat});
                visited[hat][wat] = num + 1;
            }
        }
    }
    if (wat + 1 < W) {
        if (grid[hat][wat + 1] != '.' && visited[hat][wat + 1] < 0)
        {
            if (grid[hat][wat + 1] == ch) {
                pq_vec[num].push_back({hat, wat + 1});
                visited[hat][wat + 1] = num;
            }
            else {
                pq_vec[num + 1].push_back({hat, wat + 1});
                visited[hat][wat + 1] = num + 1;
            }
        }
    }
    if (hat - 1 >= 0) {
        if (grid[hat - 1][wat] != '.' && visited[hat - 1][wat] < 0)
        {
            if (grid[hat - 1][wat] == ch) {
                pq_vec[num].push_back({hat - 1, wat});
                visited[hat - 1][wat] = num;
            }
            else {
                pq_vec[num + 1].push_back({hat - 1, wat});
                visited[hat - 1][wat] = num + 1;
            }
        }
    }
    if (wat - 1 >= 0) {
        if (grid[hat][wat - 1] != '.' && visited[hat][wat - 1] < 0)
        {
            if (grid[hat][wat - 1] == ch) {
                pq_vec[num].push_back({hat, wat - 1});
                visited[hat][wat - 1] = num;
            }
            else {
                pq_vec[num + 1].push_back({hat, wat - 1});
                visited[hat][wat - 1] = num + 1;
            }
        }
    }
}
    
int32_t main()
{
    cin>>H>>W;
    grid.assign(H, "");
    rep(i,0,H){
        cin>>grid[i];
    }
    
    visited.assign(H, vector<ll>(W, -1));
    //q.push({-1,0,0});
    ll hw10 = H*W;
    hw10 += 10;
    pq_vec.assign(hw10, {});
    pq_vec[1].push_back({0,0});
    visited[0][0] = true;

    // v

    ll i = 1;
    while(i < ll(pq_vec.size()))
    {
        ll j = 0;
        while (j < ll(pq_vec[i].size()))
        {
            pair<ll,ll> x = pq_vec[i][j];
            dfs(x.first, x.second, i);
            j++;
        }
        i++;
    }

    // ^
    
    ll ans = 1;
    rep(i,0,H){
        rep(j,0,W){
            ans = max(ans, visited[i][j]);
        }
    }
    cout << ans;
}

// pq too slow
// H*W , int * int no good, make ll = int * int
// MLE ?

Subtask #1
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 12800 KB Output isn't correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 11 ms 8688 KB Output is correct
5 Correct 4 ms 3540 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 4 ms 3028 KB Output is correct
11 Incorrect 3 ms 2640 KB Output isn't correct
12 Incorrect 6 ms 4816 KB Output isn't correct
13 Correct 4 ms 3612 KB Output is correct
14 Correct 4 ms 3540 KB Output is correct
15 Correct 16 ms 12116 KB Output is correct
16 Incorrect 18 ms 12848 KB Output isn't correct
17 Incorrect 14 ms 10588 KB Output isn't correct
18 Correct 11 ms 8640 KB Output is correct

Subtask #2
63.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2484 KB Output is correct
2 Correct 89 ms 65212 KB Output is correct
3 Correct 713 ms 627436 KB Output is correct
4 Correct 165 ms 138940 KB Output is correct
5 Correct 518 ms 437312 KB Output is correct
6 Correct 1598 ms 843356 KB Output is correct
7 Correct 3 ms 2260 KB Output is correct
8 Correct 4 ms 2388 KB Output is correct
9 Correct 3 ms 2868 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Incorrect 3 ms 2260 KB Output isn't correct
12 Correct 2 ms 1364 KB Output is correct
13 Correct 95 ms 65200 KB Output is correct
14 Correct 49 ms 38608 KB Output is correct
15 Correct 50 ms 41804 KB Output is correct
16 Correct 38 ms 29004 KB Output is correct
17 Correct 233 ms 166432 KB Output is correct
18 Correct 218 ms 162896 KB Output is correct
19 Correct 165 ms 138032 KB Output is correct
20 Correct 159 ms 137656 KB Output is correct
21 Correct 409 ms 361692 KB Output is correct
22 Correct 520 ms 436928 KB Output is correct
23 Correct 440 ms 314584 KB Output is correct
24 Correct 477 ms 376680 KB Output is correct
25 Correct 1086 ms 651256 KB Output is correct
26 Correct 829 ms 661396 KB Output is correct
27 Correct 1206 ms 865584 KB Output is correct
28 Correct 1505 ms 843292 KB Output is correct
29 Correct 1484 ms 837920 KB Output is correct
30 Correct 1346 ms 879224 KB Output is correct
31 Incorrect 952 ms 519584 KB Output isn't correct
32 Incorrect 1066 ms 798992 KB Output isn't correct