oj.uz

Submission #533956

# Submission time Handle Problem Language Result Execution time Memory
533956 2022-03-07T18:02:02 Z AbrahamJ Tracks in the Snow (BOI13_tracks) C++
100 / 100
 922 ms 159016 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 19 ms 7368 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 13 ms 7200 KB Output is correct
5 Correct 5 ms 4044 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 828 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 5 ms 3404 KB Output is correct
11 Correct 4 ms 2888 KB Output is correct
12 Correct 8 ms 4228 KB Output is correct
13 Correct 7 ms 4044 KB Output is correct
14 Correct 5 ms 4044 KB Output is correct
15 Correct 16 ms 7240 KB Output is correct
16 Correct 19 ms 7416 KB Output is correct
17 Correct 14 ms 7116 KB Output is correct
18 Correct 12 ms 7208 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 45832 KB Output is correct
2 Correct 75 ms 19964 KB Output is correct
3 Correct 440 ms 76584 KB Output is correct
4 Correct 134 ms 38604 KB Output is correct
5 Correct 247 ms 58476 KB Output is correct
6 Correct 904 ms 117240 KB Output is correct
7 Correct 56 ms 47856 KB Output is correct
8 Correct 26 ms 45768 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 29 ms 47000 KB Output is correct
12 Correct 2 ms 2124 KB Output is correct
13 Correct 81 ms 20056 KB Output is correct
14 Correct 56 ms 13888 KB Output is correct
15 Correct 33 ms 16964 KB Output is correct
16 Correct 33 ms 7236 KB Output is correct
17 Correct 146 ms 35584 KB Output is correct
18 Correct 128 ms 42456 KB Output is correct
19 Correct 103 ms 39384 KB Output is correct
20 Correct 92 ms 32064 KB Output is correct
21 Correct 219 ms 58396 KB Output is correct
22 Correct 261 ms 59076 KB Output is correct
23 Correct 286 ms 48776 KB Output is correct
24 Correct 225 ms 55800 KB Output is correct
25 Correct 519 ms 98252 KB Output is correct
26 Correct 871 ms 159016 KB Output is correct
27 Correct 911 ms 124752 KB Output is correct
28 Correct 901 ms 116592 KB Output is correct
29 Correct 902 ms 112644 KB Output is correct
30 Correct 922 ms 119988 KB Output is correct
31 Correct 635 ms 77364 KB Output is correct
32 Correct 841 ms 119284 KB Output is correct