oj.uz

Submission #636656

# Submission time Handle Problem Language Result Execution time Memory
636656 2022-08-29T21:27:26 Z LKR__enjoyer Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 1556 ms 131240 KB 
#include<bits/stdc++.h>
#include <iostream>

using namespace std;
#define f first
#define s second
int n,m;
char grid[4000][4000];
int odl[4000][4000];
pair<int,int> ruchy[4]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(int i,int j)
{
deque<pair<int,int>> w; 
w.push_front({i,j});
    while(w.empty()==0)
    {
        pair<int,int> akt=w.front();
    w.pop_front();
        for(int z=0;z<4;z++)
        {
        int u1=akt.f+ruchy[z].f;
        int u2=akt.s+ruchy[z].s;    
            if(u1<0||u1>=n||u2<0||u2>=m)continue;
        int waga=0;
            if(grid[akt.f][akt.s]!=grid[u1][u2])waga=1;
                if(odl[u1][u2]>odl[akt.f][akt.s]+waga)
                    {
                        odl[u1][u2]=odl[akt.f][akt.s]+waga;
                        if(waga==1)w.push_back({u1,u2});
                        else w.push_front({u1,u2});
                    }
        }
    }
}
int main()
{ cin>>n>>m;
for(int i=0;i<n;i++)
{for(int j=0;j<m;j++)
{   if(i||j)odl[i][j]=1e9;
    cin>>grid[i][j];
}
}
bfs(0,0);
int wynik=-1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
wynik=max(wynik,odl[i][j]);    
cout<<wynik+1;
    return 0;
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 5320 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Incorrect 1 ms 696 KB Output isn't correct
4 Correct 16 ms 5076 KB Output is correct
5 Incorrect 12 ms 3032 KB Output isn't correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Incorrect 1 ms 692 KB Output isn't correct
8 Correct 1 ms 692 KB Output is correct
9 Incorrect 2 ms 1084 KB Output isn't correct
10 Incorrect 7 ms 2656 KB Output isn't correct
11 Correct 5 ms 2132 KB Output is correct
12 Incorrect 10 ms 3028 KB Output isn't correct
13 Incorrect 9 ms 3028 KB Output isn't correct
14 Incorrect 9 ms 3072 KB Output isn't correct
15 Incorrect 26 ms 5836 KB Output isn't correct
16 Incorrect 27 ms 5284 KB Output isn't correct
17 Incorrect 25 ms 5240 KB Output isn't correct
18 Correct 16 ms 5076 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 30676 KB Output isn't correct
2 Incorrect 146 ms 21464 KB Output isn't correct
3 Incorrect 1312 ms 131240 KB Output isn't correct
4 Incorrect 344 ms 34212 KB Output isn't correct
5 Incorrect 708 ms 105076 KB Output isn't correct
6 Correct 1434 ms 101440 KB Output is correct
7 Incorrect 18 ms 32084 KB Output isn't correct
8 Incorrect 18 ms 30704 KB Output isn't correct
9 Incorrect 6 ms 724 KB Output isn't correct
10 Incorrect 3 ms 596 KB Output isn't correct
11 Incorrect 18 ms 31556 KB Output isn't correct
12 Incorrect 3 ms 1620 KB Output isn't correct
13 Incorrect 138 ms 21488 KB Output isn't correct
14 Incorrect 82 ms 13944 KB Output isn't correct
15 Incorrect 92 ms 15352 KB Output isn't correct
16 Incorrect 60 ms 8116 KB Output isn't correct
17 Incorrect 369 ms 45756 KB Output isn't correct
18 Incorrect 383 ms 44660 KB Output isn't correct
19 Incorrect 331 ms 33996 KB Output isn't correct
20 Incorrect 287 ms 40320 KB Output isn't correct
21 Incorrect 761 ms 96932 KB Output isn't correct
22 Incorrect 688 ms 104856 KB Output isn't correct
23 Incorrect 665 ms 75772 KB Output isn't correct
24 Incorrect 726 ms 94456 KB Output isn't correct
25 Incorrect 1556 ms 125416 KB Output isn't correct
26 Correct 980 ms 127996 KB Output is correct
27 Correct 1290 ms 114264 KB Output is correct
28 Correct 1374 ms 101256 KB Output is correct
29 Correct 1402 ms 99668 KB Output is correct
30 Correct 1344 ms 103748 KB Output is correct
31 Incorrect 1119 ms 71816 KB Output isn't correct
32 Incorrect 1281 ms 103068 KB Output isn't correct