oj.uz

Submission #533631

# Submission time Handle Problem Language Result Execution time Memory
533631 2022-03-06T17:28:59 Z groshi Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 794 ms 156792 KB 
#include<iostream>
#include<deque>
#include<utility>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char t[4010][4010];
bool odw[4010][4010];
int ile[4010][4010];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>t[i][j];
    deque<pair<int,pair<int,int> > > kolejka;
    kolejka.push_front({-1,{1,1}});
    odw[1][1]=1;
    int wynik=0;
    while(!kolejka.empty())
    {
        pair<int,pair<int,int> > para=kolejka.front();
        kolejka.pop_front();
        for(int i=0;i<4;i++)
        {
            int nowy_x=dx[i]+para.second.first;
            int nowy_y=dy[i]+para.second.second;
            if(nowy_x<1 || nowy_x>n || nowy_y<1 || nowy_y>m)
                continue;
            if(t[nowy_x][nowy_y]=='.')
                continue;
            if(odw[nowy_x][nowy_y]==0)
            {
                odw[nowy_x][nowy_y]=1;
                if(t[nowy_x][nowy_y]==t[para.second.first][para.second.second])
                {
                    kolejka.push_front({para.first,{nowy_x,nowy_y}});
                    ile[nowy_x][nowy_y]=-para.first;
                }
                else {
                    kolejka.push_back({para.first-1,{nowy_x,nowy_y}});
                    ile[nowy_x][nowy_y]=-para.first+1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            wynik=max(wynik,ile[i][j]);
    cout<<wynik;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7116 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 10 ms 6988 KB Output is correct
5 Correct 4 ms 3916 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 4 ms 3312 KB Output is correct
11 Correct 3 ms 2892 KB Output is correct
12 Correct 7 ms 4044 KB Output is correct
13 Correct 4 ms 3916 KB Output is correct
14 Correct 5 ms 3964 KB Output is correct
15 Correct 13 ms 7068 KB Output is correct
16 Correct 15 ms 7136 KB Output is correct
17 Correct 12 ms 6848 KB Output is correct
18 Correct 9 ms 6988 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 45800 KB Output is correct
2 Correct 56 ms 18436 KB Output is correct
3 Correct 338 ms 73356 KB Output is correct
4 Correct 101 ms 36420 KB Output is correct
5 Correct 213 ms 56360 KB Output is correct
6 Correct 782 ms 113964 KB Output is correct
7 Correct 22 ms 47820 KB Output is correct
8 Correct 21 ms 45800 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 21 ms 46980 KB Output is correct
12 Correct 2 ms 2124 KB Output is correct
13 Correct 56 ms 18488 KB Output is correct
14 Correct 32 ms 12996 KB Output is correct
15 Correct 29 ms 16012 KB Output is correct
16 Correct 24 ms 6604 KB Output is correct
17 Correct 131 ms 32600 KB Output is correct
18 Correct 111 ms 39612 KB Output is correct
19 Correct 95 ms 36420 KB Output is correct
20 Correct 86 ms 29084 KB Output is correct
21 Correct 209 ms 55632 KB Output is correct
22 Correct 211 ms 56324 KB Output is correct
23 Correct 245 ms 45764 KB Output is correct
24 Correct 201 ms 53020 KB Output is correct
25 Correct 481 ms 94468 KB Output is correct
26 Correct 739 ms 156792 KB Output is correct
27 Correct 773 ms 121404 KB Output is correct
28 Correct 794 ms 114016 KB Output is correct
29 Correct 773 ms 110900 KB Output is correct
30 Correct 767 ms 118160 KB Output is correct
31 Correct 533 ms 76368 KB Output is correct
32 Correct 755 ms 118704 KB Output is correct