oj.uz

Submission #621436

# Submission time Handle Problem Language Result Execution time Memory
621436 2022-08-03T19:17:03 Z 353cerega Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 1045 ms 180656 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;


int dp[4001][4001];

void solve()
{
    ll n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i=0;i<n;i++) cin >> s[i];
    deque<int> Q;
    Q.push_back(0);
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++) dp[i][j] = mod;
    }
    dp[0][0] = 0;
    vector<int> was(n*m);
    vector<int> dx = {1,-1,0,0};
    vector<int> dy = {0,0,1,-1};
    while (Q.size()>0)
    {
        int p = Q.front();
        Q.pop_front();
        if (was[p]==1) continue;
        was[p] = 1;
        int x = p/m;
        int y = p-m*x;
        for (int d=0;d<4;d++)
        {
            int x2 = x+dx[d];
            int y2 = y+dy[d];
            if (x2>=n or x2<0 or y2>=m or y2<0) continue;
            int W = dp[x][y];
            int F = 0;
            if (s[x][y]!=s[x2][y2]) F = 1;
            if (dp[x2][y2]>W+F)
            {
                dp[x2][y2] = W+F;
                if (F==0) Q.push_front(x2*m+y2);
                else Q.push_back(x2*m+y2);
            }
        }
    }
    int A = 0;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            if (dp[i][j]<mod) A = max(A,dp[i][j]);
        }
    }
    cout << A+1 << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4692 KB Output isn't correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Correct 7 ms 3924 KB Output is correct
5 Incorrect 4 ms 2260 KB Output isn't correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Incorrect 1 ms 452 KB Output isn't correct
8 Correct 1 ms 596 KB Output is correct
9 Incorrect 1 ms 724 KB Output isn't correct
10 Incorrect 4 ms 2004 KB Output isn't correct
11 Correct 3 ms 1492 KB Output is correct
12 Incorrect 6 ms 2388 KB Output isn't correct
13 Incorrect 5 ms 2260 KB Output isn't correct
14 Incorrect 4 ms 2260 KB Output isn't correct
15 Incorrect 15 ms 5016 KB Output isn't correct
16 Incorrect 16 ms 4684 KB Output isn't correct
17 Incorrect 14 ms 4564 KB Output isn't correct
18 Correct 8 ms 3900 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16244 KB Output isn't correct
2 Incorrect 68 ms 22672 KB Output isn't correct
3 Incorrect 580 ms 180656 KB Output isn't correct
4 Incorrect 164 ms 45132 KB Output isn't correct
5 Incorrect 283 ms 119756 KB Output isn't correct
6 Correct 707 ms 165884 KB Output is correct
7 Incorrect 9 ms 16980 KB Output isn't correct
8 Incorrect 8 ms 16200 KB Output isn't correct
9 Incorrect 3 ms 980 KB Output isn't correct
10 Incorrect 1 ms 728 KB Output isn't correct
11 Incorrect 8 ms 16720 KB Output isn't correct
12 Incorrect 2 ms 1112 KB Output isn't correct
13 Incorrect 67 ms 22624 KB Output isn't correct
14 Incorrect 38 ms 13896 KB Output isn't correct
15 Incorrect 51 ms 15488 KB Output isn't correct
16 Incorrect 29 ms 8940 KB Output isn't correct
17 Incorrect 159 ms 53268 KB Output isn't correct
18 Incorrect 220 ms 52428 KB Output isn't correct
19 Incorrect 177 ms 45164 KB Output isn't correct
20 Incorrect 127 ms 46000 KB Output isn't correct
21 Incorrect 317 ms 118396 KB Output isn't correct
22 Incorrect 286 ms 119780 KB Output isn't correct
23 Incorrect 310 ms 95300 KB Output isn't correct
24 Incorrect 301 ms 115200 KB Output isn't correct
25 Incorrect 1045 ms 177904 KB Output isn't correct
26 Correct 380 ms 153696 KB Output is correct
27 Correct 506 ms 172392 KB Output is correct
28 Correct 710 ms 165816 KB Output is correct
29 Correct 685 ms 165116 KB Output is correct
30 Correct 618 ms 164712 KB Output is correct
31 Incorrect 661 ms 111948 KB Output isn't correct
32 Incorrect 511 ms 166812 KB Output isn't correct