oj.uz

Submission #769761

# Submission time Handle Problem Language Result Execution time Memory
769761 2023-06-30T08:21:55 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 1956 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, {});
        pq_vec[1].push_back({0,0});

        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:54:17: 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]
   54 |         while(i < pq_vec.size())
      |               ~~^~~~~~~~~~~~~~~
tracks.cpp:57:22: 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]
   57 |             while (j < pq_vec[i].size())
      |                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 23400 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 424 KB Output is correct
4 Correct 22 ms 20772 KB Output is correct
5 Correct 6 ms 4584 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 5 ms 4436 KB Output is correct
11 Correct 6 ms 5868 KB Output is correct
12 Correct 15 ms 8528 KB Output is correct
13 Correct 6 ms 4564 KB Output is correct
14 Correct 6 ms 4672 KB Output is correct
15 Correct 28 ms 20500 KB Output is correct
16 Correct 32 ms 23448 KB Output is correct
17 Correct 20 ms 15476 KB Output is correct
18 Correct 21 ms 20684 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 130 ms 95776 KB Output is correct
3 Correct 1202 ms 873960 KB Output is correct
4 Correct 231 ms 165712 KB Output is correct
5 Correct 897 ms 647908 KB Output is correct
6 Runtime error 1551 ms 1048576 KB Execution killed with signal 9
7 Correct 4 ms 2900 KB Output is correct
8 Correct 4 ms 3156 KB Output is correct
9 Correct 6 ms 4480 KB Output is correct
10 Correct 2 ms 2004 KB Output is correct
11 Correct 4 ms 2592 KB Output is correct
12 Correct 3 ms 1844 KB Output is correct
13 Correct 147 ms 95672 KB Output is correct
14 Correct 79 ms 56616 KB Output is correct
15 Correct 91 ms 59140 KB Output is correct
16 Correct 63 ms 45660 KB Output is correct
17 Correct 400 ms 245912 KB Output is correct
18 Correct 350 ms 232512 KB Output is correct
19 Correct 231 ms 166784 KB Output is correct
20 Correct 247 ms 197584 KB Output is correct
21 Correct 637 ms 510940 KB Output is correct
22 Correct 891 ms 649040 KB Output is correct
23 Correct 799 ms 467912 KB Output is correct
24 Correct 709 ms 560272 KB Output is correct
25 Correct 1443 ms 929868 KB Output is correct
26 Runtime error 1312 ms 1048576 KB Execution killed with signal 9
27 Runtime error 976 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1458 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1524 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1560 ms 1048576 KB Execution killed with signal 9
31 Correct 1956 ms 977652 KB Output is correct
32 Runtime error 981 ms 1048576 KB Execution killed with signal 9