Submission #624144

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624144	2022-08-07T10:25:13 Z	lam	Tracks in the Snow (BOI13_tracks)	C++14	70.9375 / 100	697 ms	144128 KB

tracks

#include <bits/stdc++.h>
#define maxn 4010
using namespace std;

int n,m,dp[maxn][maxn],ans=1;
char a[maxn][maxn];
deque<pair<int,int>> q;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

bool in(int x, int y)
{
    if (x<1||x>n) return 0;
    if (y<1||y>n) return 0;
    return a[x][y]!='.';
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>m;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++) cin>>a[i][j],dp[i][j]=0;
    dp[1][1]=1;
    q.push_back({1,1});
    while (!q.empty())
    {
        int u=q.front().first;
        int v=q.front().second;
        ans=max(ans,dp[u][v]);
        q.pop_front();
        for (int c=0; c<4; c++)
        {
            int i=u+dx[c]; int j=v+dy[c];
            if (in(i,j)&&dp[i][j]==0)
            {
                if (a[i][j]==a[u][v]){
                    dp[i][j]=dp[u][v];
                    q.push_front({i,j});
                }
                else {
                    dp[i][j]=dp[u][v]+1;
                    q.push_back({i,j});
                }
            }
        }
    }
    cout<<ans;
}

Subtask #1

25.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	12 ms	5336 KB	Output isn't correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	724 KB	Output is correct
4	Correct	10 ms	5724 KB	Output is correct
5	Correct	3 ms	3028 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	732 KB	Output is correct
8	Incorrect	1 ms	728 KB	Output isn't correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	3 ms	2644 KB	Output is correct
11	Correct	3 ms	2140 KB	Output is correct
12	Correct	5 ms	3036 KB	Output is correct
13	Correct	3 ms	3036 KB	Output is correct
14	Correct	4 ms	3036 KB	Output is correct
15	Correct	14 ms	5444 KB	Output is correct
16	Incorrect	12 ms	5364 KB	Output isn't correct
17	Correct	10 ms	5212 KB	Output is correct
18	Correct	9 ms	5724 KB	Output is correct

Subtask #2

45.9375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	566 ms	134848 KB	Output isn't correct
2	Correct	49 ms	16536 KB	Output is correct
3	Correct	314 ms	78924 KB	Output is correct
4	Incorrect	91 ms	30016 KB	Output isn't correct
5	Correct	230 ms	59232 KB	Output is correct
6	Correct	697 ms	93272 KB	Output is correct
7	Correct	559 ms	144128 KB	Output is correct
8	Incorrect	569 ms	134804 KB	Output isn't correct
9	Incorrect	1 ms	596 KB	Output isn't correct
10	Incorrect	1 ms	468 KB	Output isn't correct
11	Correct	532 ms	140236 KB	Output is correct
12	Correct	2 ms	1620 KB	Output is correct
13	Correct	49 ms	16532 KB	Output is correct
14	Incorrect	28 ms	11220 KB	Output isn't correct
15	Correct	28 ms	12244 KB	Output is correct
16	Incorrect	10 ms	6152 KB	Output isn't correct
17	Correct	123 ms	32324 KB	Output is correct
18	Correct	115 ms	31860 KB	Output is correct
19	Incorrect	94 ms	30064 KB	Output isn't correct
20	Incorrect	51 ms	27832 KB	Output isn't correct
21	Correct	196 ms	62548 KB	Output is correct
22	Correct	218 ms	59292 KB	Output is correct
23	Incorrect	203 ms	49616 KB	Output isn't correct
24	Correct	219 ms	64076 KB	Output is correct
25	Correct	464 ms	78916 KB	Output is correct
26	Correct	581 ms	119256 KB	Output is correct
27	Correct	640 ms	104572 KB	Output is correct
28	Correct	667 ms	93364 KB	Output is correct
29	Correct	685 ms	90680 KB	Output is correct
30	Correct	658 ms	95744 KB	Output is correct
31	Incorrect	454 ms	63788 KB	Output isn't correct
32	Correct	623 ms	102976 KB	Output is correct