oj.uz

Submission #769857

# Submission time Handle Problem Language Result Execution time Memory
769857 2023-06-30T11:35:03 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 1814 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;
    hw10 += 10;
    pq_vec.assign(hw10, {});
    pq_vec[1].push_back({0,0});

    // 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;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23436 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 24 ms 20732 KB Output is correct
5 Correct 5 ms 4564 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 724 KB Output is correct
10 Correct 5 ms 4436 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 4664 KB Output is correct
14 Correct 5 ms 4564 KB Output is correct
15 Correct 29 ms 20492 KB Output is correct
16 Correct 34 ms 23440 KB Output is correct
17 Correct 22 ms 15416 KB Output is correct
18 Correct 22 ms 20672 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3128 KB Output is correct
2 Correct 131 ms 94780 KB Output is correct
3 Correct 949 ms 873284 KB Output is correct
4 Correct 209 ms 163784 KB Output is correct
5 Correct 822 ms 646100 KB Output is correct
6 Runtime error 1457 ms 1048576 KB Execution killed with signal 9
7 Correct 4 ms 2872 KB Output is correct
8 Correct 4 ms 3164 KB Output is correct
9 Correct 5 ms 4480 KB Output is correct
10 Correct 2 ms 1972 KB Output is correct
11 Correct 3 ms 2616 KB Output is correct
12 Correct 3 ms 1876 KB Output is correct
13 Correct 137 ms 94272 KB Output is correct
14 Correct 78 ms 55868 KB Output is correct
15 Correct 80 ms 58356 KB Output is correct
16 Correct 63 ms 45184 KB Output is correct
17 Correct 379 ms 242460 KB Output is correct
18 Correct 308 ms 228956 KB Output is correct
19 Correct 213 ms 163356 KB Output is correct
20 Correct 246 ms 194388 KB Output is correct
21 Correct 581 ms 507564 KB Output is correct
22 Correct 823 ms 645680 KB Output is correct
23 Correct 719 ms 464380 KB Output is correct
24 Correct 666 ms 556964 KB Output is correct
25 Correct 1420 ms 926564 KB Output is correct
26 Runtime error 1237 ms 1048576 KB Execution killed with signal 9
27 Runtime error 942 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1475 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1422 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1511 ms 1048576 KB Execution killed with signal 9
31 Correct 1814 ms 973996 KB Output is correct
32 Runtime error 955 ms 1048576 KB Execution killed with signal 9