oj.uz

Submission #769853

# Submission time Handle Problem Language Result Execution time Memory
769853 2023-06-30T11:21:58 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 1795 ms 1048576 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)
{
    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] == ch) pq_vec[num].push_back({hat + 1, wat});
        else pq_vec[num + 1].push_back({hat + 1, wat});
    }
    if (wat + 1 < W) {
        if (grid[hat][wat + 1] == ch) pq_vec[num].push_back({hat, wat + 1});
        else pq_vec[num + 1].push_back({hat, wat + 1});
    }
    if (hat - 1 >= 0) {
        if (grid[hat - 1][wat] == ch) pq_vec[num].push_back({hat - 1, wat});
        else pq_vec[num + 1].push_back({hat - 1, wat});
    }
    if (wat - 1 >= 0) {
        if (grid[hat][wat - 1] == ch) pq_vec[num].push_back({hat, wat - 1});
        else pq_vec[num + 1].push_back({hat, wat - 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});
    pq_vec.assign(H*W + 10, {});
    pq_vec[1].push_back({0,0});

    // v

    ll i = 1;
    while(i < pq_vec.size())
    {
        ll j = 0;
        while (j < 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;
}

Compilation message

tracks.cpp: In function 'int32_t main()':
tracks.cpp:56:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while(i < pq_vec.size())
      |           ~~^~~~~~~~~~~~~~~
tracks.cpp:59:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (j < pq_vec[i].size())
      |                ~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 23400 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 21 ms 20708 KB Output is correct
5 Correct 5 ms 4632 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 820 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 6 ms 4404 KB Output is correct
11 Correct 6 ms 5768 KB Output is correct
12 Correct 11 ms 8528 KB Output is correct
13 Correct 5 ms 4564 KB Output is correct
14 Correct 5 ms 4608 KB Output is correct
15 Correct 28 ms 20456 KB Output is correct
16 Correct 32 ms 23392 KB Output is correct
17 Correct 21 ms 15456 KB Output is correct
18 Correct 25 ms 20632 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3132 KB Output is correct
2 Correct 133 ms 95768 KB Output is correct
3 Correct 1128 ms 877280 KB Output is correct
4 Correct 251 ms 165528 KB Output is correct
5 Correct 865 ms 649424 KB Output is correct
6 Runtime error 1508 ms 1048576 KB Execution killed with signal 9
7 Correct 8 ms 2900 KB Output is correct
8 Correct 5 ms 3156 KB Output is correct
9 Correct 7 ms 4480 KB Output is correct
10 Correct 2 ms 2004 KB Output is correct
11 Correct 3 ms 2648 KB Output is correct
12 Correct 3 ms 1876 KB Output is correct
13 Correct 134 ms 95712 KB Output is correct
14 Correct 78 ms 56632 KB Output is correct
15 Correct 92 ms 59160 KB Output is correct
16 Correct 63 ms 45672 KB Output is correct
17 Correct 356 ms 245568 KB Output is correct
18 Correct 314 ms 232304 KB Output is correct
19 Correct 207 ms 166348 KB Output is correct
20 Correct 227 ms 197244 KB Output is correct
21 Correct 583 ms 512632 KB Output is correct
22 Correct 863 ms 650732 KB Output is correct
23 Correct 715 ms 469284 KB Output is correct
24 Correct 688 ms 561812 KB Output is correct
25 Correct 1389 ms 931480 KB Output is correct
26 Runtime error 1183 ms 1048576 KB Execution killed with signal 9
27 Runtime error 942 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1425 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1438 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1507 ms 1048576 KB Execution killed with signal 9
31 Correct 1795 ms 978892 KB Output is correct
32 Runtime error 988 ms 1048576 KB Execution killed with signal 9