oj.uz

Submission #769855

# Submission time Handle Problem Language Result Execution time Memory
769855 2023-06-30T11:31:30 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 1967 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)
{
    //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] == 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});
    ll hw10 = H*W + 10;
    pq_vec.assign(hw10, {});
    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:58: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]
   58 |     while(i < pq_vec.size())
      |           ~~^~~~~~~~~~~~~~~
tracks.cpp:61: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]
   61 |         while (j < pq_vec[i].size())
      |                ~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23500 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 23 ms 20672 KB Output is correct
5 Correct 5 ms 4664 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 852 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 5 ms 4436 KB Output is correct
11 Correct 6 ms 5760 KB Output is correct
12 Correct 13 ms 8460 KB Output is correct
13 Correct 6 ms 4648 KB Output is correct
14 Correct 5 ms 4632 KB Output is correct
15 Correct 30 ms 20592 KB Output is correct
16 Correct 34 ms 23500 KB Output is correct
17 Correct 26 ms 15380 KB Output is correct
18 Correct 22 ms 20664 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3156 KB Output is correct
2 Correct 155 ms 94772 KB Output is correct
3 Correct 1114 ms 876848 KB Output is correct
4 Correct 208 ms 164128 KB Output is correct
5 Correct 922 ms 647184 KB Output is correct
6 Runtime error 1537 ms 1048576 KB Execution killed with signal 9
7 Correct 4 ms 2956 KB Output is correct
8 Correct 7 ms 3156 KB Output is correct
9 Correct 6 ms 4480 KB Output is correct
10 Correct 2 ms 1976 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 3 ms 1880 KB Output is correct
13 Correct 156 ms 94532 KB Output is correct
14 Correct 79 ms 56004 KB Output is correct
15 Correct 98 ms 58444 KB Output is correct
16 Correct 69 ms 45328 KB Output is correct
17 Correct 401 ms 242948 KB Output is correct
18 Correct 369 ms 229500 KB Output is correct
19 Correct 229 ms 163840 KB Output is correct
20 Correct 242 ms 194772 KB Output is correct
21 Correct 635 ms 508584 KB Output is correct
22 Correct 880 ms 646608 KB Output is correct
23 Correct 789 ms 465272 KB Output is correct
24 Correct 739 ms 557780 KB Output is correct
25 Correct 1534 ms 928304 KB Output is correct
26 Runtime error 1308 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1118 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1505 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1524 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1619 ms 1048576 KB Execution killed with signal 9
31 Correct 1967 ms 973748 KB Output is correct
32 Runtime error 1034 ms 1048576 KB Execution killed with signal 9