oj.uz

Submission #769867

# Submission time Handle Problem Language Result Execution time Memory
769867 2023-06-30T12:03:09 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 522 ms 538132 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]))
        {
            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]))
        {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]))
        {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]))
        {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 ?

Compilation message

tracks.cpp: In function 'void dfs(int, int, ll)':
tracks.cpp:40:35: warning: value computed is not used [-Wunused-value]
   40 |             visited[hat][wat + 1] == num;
tracks.cpp:44:35: warning: value computed is not used [-Wunused-value]
   44 |             visited[hat][wat + 1] == num + 1;
tracks.cpp:51:35: warning: value computed is not used [-Wunused-value]
   51 |             visited[hat - 1][wat] == num;
tracks.cpp:55:35: warning: value computed is not used [-Wunused-value]
   55 |             visited[hat - 1][wat] == num + 1;
tracks.cpp:62:35: warning: value computed is not used [-Wunused-value]
   62 |             visited[hat][wat - 1] == num;
tracks.cpp:66:35: warning: value computed is not used [-Wunused-value]
   66 |             visited[hat][wat - 1] == num + 1;

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8404 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 5 ms 5460 KB Output isn't correct
5 Incorrect 3 ms 3156 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 304 KB Output isn't correct
8 Incorrect 1 ms 424 KB Output isn't correct
9 Incorrect 1 ms 596 KB Output isn't correct
10 Incorrect 3 ms 2516 KB Output isn't correct
11 Incorrect 2 ms 1620 KB Output isn't correct
12 Incorrect 3 ms 3156 KB Output isn't correct
13 Incorrect 3 ms 3156 KB Output isn't correct
14 Incorrect 3 ms 3156 KB Output isn't correct
15 Incorrect 8 ms 8660 KB Output isn't correct
16 Incorrect 8 ms 8396 KB Output isn't correct
17 Incorrect 8 ms 8276 KB Output isn't correct
18 Incorrect 5 ms 5460 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2132 KB Output isn't correct
2 Incorrect 51 ms 51776 KB Output isn't correct
3 Incorrect 522 ms 531720 KB Output isn't correct
4 Incorrect 118 ms 124976 KB Output isn't correct
5 Incorrect 275 ms 293800 KB Output isn't correct
6 Incorrect 496 ms 537908 KB Output isn't correct
7 Incorrect 2 ms 1876 KB Output isn't correct
8 Incorrect 4 ms 2004 KB Output isn't correct
9 Incorrect 2 ms 2260 KB Output isn't correct
10 Incorrect 2 ms 1364 KB Output isn't correct
11 Incorrect 2 ms 2004 KB Output isn't correct
12 Incorrect 1 ms 980 KB Output isn't correct
13 Incorrect 51 ms 51676 KB Output isn't correct
14 Incorrect 30 ms 30252 KB Output isn't correct
15 Incorrect 33 ms 33484 KB Output isn't correct
16 Incorrect 21 ms 21068 KB Output isn't correct
17 Incorrect 127 ms 134884 KB Output isn't correct
18 Incorrect 124 ms 133164 KB Output isn't correct
19 Incorrect 122 ms 124888 KB Output isn't correct
20 Incorrect 109 ms 114688 KB Output isn't correct
21 Incorrect 282 ms 303700 KB Output isn't correct
22 Incorrect 277 ms 293600 KB Output isn't correct
23 Incorrect 234 ms 252324 KB Output isn't correct
24 Incorrect 271 ms 296884 KB Output isn't correct
25 Incorrect 484 ms 531724 KB Output isn't correct
26 Correct 372 ms 402764 KB Output is correct
27 Incorrect 506 ms 538060 KB Output isn't correct
28 Incorrect 493 ms 538036 KB Output isn't correct
29 Incorrect 491 ms 538080 KB Output isn't correct
30 Incorrect 479 ms 527000 KB Output isn't correct
31 Incorrect 311 ms 333520 KB Output isn't correct
32 Incorrect 506 ms 538132 KB Output isn't correct