oj.uz

Submission #581540

# Submission time Handle Problem Language Result Execution time Memory
581540 2022-06-22T17:39:03 Z alexdd Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1554 ms 122036 KB 
#include<iostream>
#include<deque>
using namespace std;
int n,m;
char mat[4001][4001];
int dirlin[4]={1,-1,0,0};
int dircol[4]={0,0,1,-1};
deque<int> dqlin;
deque<int> dqcol;
int best[4001][4001];
bool good(int lin, int col)
{
    if(lin>=1 && lin<=n && col>=1 && col<=m)
        return 1;
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {cin>>mat[i][j];best[i][j]=4000*4000+100;}
    dqlin.push_back(1);
    dqcol.push_back(1);
    best[1][1]=1;
    int lin,col;
    while(dqlin.empty()==0)
    {
        lin=dqlin.front();
        col=dqcol.front();
        dqlin.pop_front();
        dqcol.pop_front();
        for(int i=0;i<4;i++)
        {
            if(good(lin+dirlin[i], col+dircol[i]) && mat[lin+dirlin[i]][col+dircol[i]]!='.' && best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])<best[lin+dirlin[i]][col+dircol[i]])
            {
                best[lin+dirlin[i]][col+dircol[i]]=best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]]);
                if(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])
                {
                    dqlin.push_back(lin+dirlin[i]);
                    dqcol.push_back(col+dircol[i]);
                }
                else
                {
                    dqlin.push_front(lin+dirlin[i]);
                    dqcol.push_front(col+dircol[i]);

                }
            }
        }
    }
    int mxm=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(mat[i][j]!='.')
                mxm=max(mxm,best[i][j]);
    }
    cout<<mxm;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5332 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 16 ms 5076 KB Output is correct
5 Correct 8 ms 2924 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 7 ms 2516 KB Output is correct
11 Correct 6 ms 2132 KB Output is correct
12 Correct 11 ms 3084 KB Output is correct
13 Correct 8 ms 2976 KB Output is correct
14 Correct 10 ms 3028 KB Output is correct
15 Correct 25 ms 5508 KB Output is correct
16 Correct 26 ms 5408 KB Output is correct
17 Correct 22 ms 5204 KB Output is correct
18 Correct 15 ms 5076 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30796 KB Output is correct
2 Correct 130 ms 17924 KB Output is correct
3 Correct 1122 ms 81660 KB Output is correct
4 Correct 283 ms 33416 KB Output is correct
5 Correct 683 ms 62208 KB Output is correct
6 Correct 1554 ms 95308 KB Output is correct
7 Correct 23 ms 32280 KB Output is correct
8 Correct 19 ms 30784 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 17 ms 31696 KB Output is correct
12 Correct 3 ms 1620 KB Output is correct
13 Correct 126 ms 17912 KB Output is correct
14 Correct 78 ms 11840 KB Output is correct
15 Correct 79 ms 13064 KB Output is correct
16 Correct 54 ms 6564 KB Output is correct
17 Correct 325 ms 35628 KB Output is correct
18 Correct 338 ms 35472 KB Output is correct
19 Correct 278 ms 33412 KB Output is correct
20 Correct 251 ms 30992 KB Output is correct
21 Correct 665 ms 63976 KB Output is correct
22 Correct 652 ms 62276 KB Output is correct
23 Correct 631 ms 52704 KB Output is correct
24 Correct 658 ms 63528 KB Output is correct
25 Correct 1239 ms 81708 KB Output is correct
26 Correct 1041 ms 122036 KB Output is correct
27 Correct 1370 ms 108328 KB Output is correct
28 Correct 1484 ms 95188 KB Output is correct
29 Correct 1468 ms 93712 KB Output is correct
30 Correct 1415 ms 98088 KB Output is correct
31 Correct 1112 ms 66456 KB Output is correct
32 Correct 1276 ms 97008 KB Output is correct