oj.uz

Submission #958665

# Submission time Handle Problem Language Result Execution time Memory
958665 2024-04-06T10:04:38 Z ramalzaher Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 890 ms 349852 KB 
/** * * * * * * * * * * * * * **\
 *                             *
 *   Author:Ram Azar Alzaher   *
 * Coded in: YYYY\M\D HH:MM:SS *
 *          Lang: C++          *
 *                             *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define vi vector< int >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define s(i) set< i >
#define us(i) unordered_set< i >
#define set set<int>
#define uset unordered_set<int>
#define mp make_pair
#define f first
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
#define so(x) sort(all(s))
#define so(x) sort(all(s))
#define s second
#define sz size()
#define pb push_back
#define test long long t ;cin >> t ;while(t--)
using namespace std;
//*****************************************************VARIABLES***************************************************************\\\\*******************************\\
//*****************************************************************************************************************************\\\\
//***************************************************************************************************************************************
const double pi=2.0*acos(0.0);
const int inf=1LL<<62LL;
const int mod=1e9+7;
int dx[] {1,-1,0,0};
int dy[] {0,0,1,-1};
int max1 = INT_MIN;
int min1 = INT_MAX;
//*****************************************************************************************************************************\\\\
//**************************************************************************************************************************************
//******************************************************************************************************************************\****************


//*****************************************************FUNCTIONS***************************************************************\\\\*******************************\\
//*****************************************************************************************************************************\\\\
//***************************************************************************************************************************************
void setIO(string name = "")
{
    if(name != "")
    {

        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}
const int N = 4004 ;
int n, m ;
string a[N] ;
int vis[N][N], dis[N][N];
bool isvalid(int x,int y  )
{
    if(x >= n || y >= m || y < 0 || x < 0 )return 0 ;
    if( vis[x][y] ==1 || a[x][y] == '.' )return 0 ;
    return 1 ;
}

//*****************************************************************************************************************************\\\\
//**************************************************************************************************************************************
//******************************************************************************************************************************\****************


signed main()
{
    cin >> n >> m ;
    FOR(i, n )cin >> a[i] ;
    memset(dis , 0 , sizeof dis ) ;
    deque<pii> q ;
    q.push_back({0,0});
    dis[0][0] = 1 ;vis[0][0]= 1;
    int ans = 1  ;
    while(q.sz)
    {
        auto [x, y ] = q.front() ;
        q.pop_front() ;
        ans=max(ans, dis[x][y] ) ;
        FOR(i,  4)
        {
            int nx = dx[i]+x;
            int ny = dy[i]+y;
            if(isvalid(nx, ny ))
            {
                if( a[x][y] == a[nx][ny] )
                {
                    q.push_front({nx, ny });
                    dis[nx][ny] = dis[x][y] ;
                    vis[nx][ny] = 1 ;
                }
                else
                {
                    q.push_back({nx, ny });
                    dis[nx][ny] = dis[x][y] + 1 ;
                    vis[nx][ny] = 1 ;
                }
            }
        }
    }
    cout<< ans << endl ;

    return 0 ;
}
/**
input :


output :
*/

Compilation message

tracks.cpp:32: warning: "s" redefined
   32 | #define s second
      | 
tracks.cpp:22: note: this is the location of the previous definition
   22 | #define s(i) set< i >
      | 
tracks.cpp:37:1: warning: multi-line comment [-Wcomment]
   37 | //*****************************************************VARIABLES***************************************************************\\\\*******************************\\
      | ^
tracks.cpp:47:1: warning: multi-line comment [-Wcomment]
   47 | //*****************************************************************************************************************************\\\\
      | ^
tracks.cpp:52:1: warning: multi-line comment [-Wcomment]
   52 | //*****************************************************FUNCTIONS***************************************************************\\\\*******************************\\
      | ^
tracks.cpp:75:1: warning: multi-line comment [-Wcomment]
   75 | //*****************************************************************************************************************************\\\\
      | ^
tracks.cpp: In function 'int main()':
tracks.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |         auto [x, y ] = q.front() ;
      |              ^
tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 131804 KB Output is correct
2 Correct 18 ms 127832 KB Output is correct
3 Correct 16 ms 127836 KB Output is correct
4 Correct 26 ms 131212 KB Output is correct
5 Correct 20 ms 129372 KB Output is correct
6 Correct 19 ms 127836 KB Output is correct
7 Correct 16 ms 127836 KB Output is correct
8 Correct 19 ms 127804 KB Output is correct
9 Correct 17 ms 127976 KB Output is correct
10 Correct 19 ms 128860 KB Output is correct
11 Correct 20 ms 128860 KB Output is correct
12 Correct 21 ms 129628 KB Output is correct
13 Correct 20 ms 129372 KB Output is correct
14 Correct 20 ms 129256 KB Output is correct
15 Correct 31 ms 131412 KB Output is correct
16 Correct 30 ms 131852 KB Output is correct
17 Correct 27 ms 131420 KB Output is correct
18 Correct 26 ms 131236 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 143192 KB Output is correct
2 Correct 78 ms 141132 KB Output is correct
3 Correct 379 ms 216656 KB Output is correct
4 Correct 128 ms 169296 KB Output is correct
5 Correct 250 ms 188516 KB Output is correct
6 Correct 890 ms 308384 KB Output is correct
7 Correct 27 ms 143964 KB Output is correct
8 Correct 30 ms 143276 KB Output is correct
9 Correct 18 ms 128092 KB Output is correct
10 Correct 20 ms 128088 KB Output is correct
11 Correct 25 ms 143700 KB Output is correct
12 Correct 17 ms 128348 KB Output is correct
13 Correct 70 ms 141132 KB Output is correct
14 Correct 48 ms 136784 KB Output is correct
15 Correct 54 ms 140836 KB Output is correct
16 Correct 40 ms 132692 KB Output is correct
17 Correct 165 ms 158988 KB Output is correct
18 Correct 146 ms 173524 KB Output is correct
19 Correct 129 ms 169396 KB Output is correct
20 Correct 100 ms 153684 KB Output is correct
21 Correct 229 ms 180104 KB Output is correct
22 Correct 252 ms 188448 KB Output is correct
23 Correct 292 ms 176196 KB Output is correct
24 Correct 220 ms 179188 KB Output is correct
25 Correct 719 ms 281604 KB Output is correct
26 Correct 476 ms 349852 KB Output is correct
27 Correct 641 ms 334644 KB Output is correct
28 Correct 817 ms 308404 KB Output is correct
29 Correct 815 ms 305424 KB Output is correct
30 Correct 734 ms 314028 KB Output is correct
31 Correct 661 ms 232300 KB Output is correct
32 Correct 576 ms 305828 KB Output is correct