oj.uz

Submission #958666

# Submission time Handle Problem Language Result Execution time Memory
958666 2024-04-06T10:05:23 Z ramalzaher Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 890 ms 349352 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() ;
        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 ;
                }
            }
        }
    }
    ans = dis[n-1][m-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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 131888 KB Output isn't correct
2 Incorrect 16 ms 127836 KB Output isn't correct
3 Incorrect 18 ms 127828 KB Output isn't correct
4 Incorrect 24 ms 131156 KB Output isn't correct
5 Incorrect 20 ms 129304 KB Output isn't correct
6 Incorrect 16 ms 127832 KB Output isn't correct
7 Incorrect 17 ms 127836 KB Output isn't correct
8 Incorrect 17 ms 127836 KB Output isn't correct
9 Incorrect 16 ms 128092 KB Output isn't correct
10 Incorrect 19 ms 129040 KB Output isn't correct
11 Incorrect 18 ms 128860 KB Output isn't correct
12 Incorrect 23 ms 129372 KB Output isn't correct
13 Incorrect 20 ms 129372 KB Output isn't correct
14 Incorrect 20 ms 129228 KB Output isn't correct
15 Incorrect 32 ms 131412 KB Output isn't correct
16 Incorrect 31 ms 131664 KB Output isn't correct
17 Incorrect 28 ms 131636 KB Output isn't correct
18 Incorrect 29 ms 131352 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 143296 KB Output isn't correct
2 Incorrect 82 ms 141108 KB Output isn't correct
3 Incorrect 374 ms 216728 KB Output isn't correct
4 Incorrect 128 ms 169392 KB Output isn't correct
5 Incorrect 252 ms 188640 KB Output isn't correct
6 Incorrect 890 ms 308464 KB Output isn't correct
7 Incorrect 26 ms 143964 KB Output isn't correct
8 Incorrect 25 ms 143196 KB Output isn't correct
9 Incorrect 18 ms 128092 KB Output isn't correct
10 Incorrect 17 ms 127836 KB Output isn't correct
11 Incorrect 26 ms 143696 KB Output isn't correct
12 Incorrect 17 ms 128348 KB Output isn't correct
13 Incorrect 73 ms 141136 KB Output isn't correct
14 Incorrect 47 ms 136716 KB Output isn't correct
15 Incorrect 48 ms 140908 KB Output isn't correct
16 Incorrect 40 ms 132692 KB Output isn't correct
17 Incorrect 168 ms 159056 KB Output isn't correct
18 Incorrect 155 ms 173720 KB Output isn't correct
19 Incorrect 127 ms 169340 KB Output isn't correct
20 Incorrect 103 ms 153684 KB Output isn't correct
21 Incorrect 246 ms 180228 KB Output isn't correct
22 Incorrect 250 ms 188424 KB Output isn't correct
23 Incorrect 308 ms 176256 KB Output isn't correct
24 Incorrect 228 ms 179092 KB Output isn't correct
25 Incorrect 751 ms 281524 KB Output isn't correct
26 Correct 529 ms 349352 KB Output is correct
27 Incorrect 648 ms 334624 KB Output isn't correct
28 Incorrect 811 ms 308600 KB Output isn't correct
29 Incorrect 798 ms 305520 KB Output isn't correct
30 Incorrect 753 ms 314100 KB Output isn't correct
31 Incorrect 625 ms 231992 KB Output isn't correct
32 Incorrect 587 ms 306012 KB Output isn't correct