oj.uz

Submission #956607

# Submission time Handle Problem Language Result Execution time Memory
956607 2024-04-02T08:24:59 Z Kladness Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 567 ms 228808 KB 
#include <bits/stdc++.h>

#include <cmath>
#include <chrono>
#include <numeric>

using namespace std;
#define fasterio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n"
#define ll long long
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
#define int long long
//#define double long double
#define pb push_back

#define dbugvec(v) for(int i=0;i<v.size();i++){ cout << v[i] << " ";}cout << endl;
#define dbugarr(arr) for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++){ cout << arr[i] << " ";}cout << endl;
#define dbug2dvec(v) for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++){cout << v[i][j] << " ";}cout << endl;}
ll mod= 1e9+7;
//ll N = 252000;
ll inf = 1e18;
double e=2.718281828459045235360;


//FUNCTIONS
ll inv(ll a, ll b = mod) { return 1 < a ? b - inv(b % a, a) * b / a : 1; }
bool cmp(pair<int,int> a,pair<int,int> b){ return a.second>b.second;}
int binpow(int a, int b, int m) {
    a %= m;
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll C(int n, int k,vector<int>&fact,vector<int>&invfact) {
    if (k > n) {
        return 0;
    }
    return fact[n] * invfact[k] % mod * invfact[n - k] % mod;
}


int recur(int i, int left, vector<int> &v, vector<vector<int>> &dp, int no)
{
    if(i==v.size()) return 0;
    if(v[i]==0)
    {
        int alpha = recur(i+1,left-1,v,dp,0);
        int beta;
        if(v[i]==no)
            {
                 beta = recur(i+1,left,v,dp,no+1) ;
            }
        else
        {
             beta = recur(i+1,left,v,dp,no+1) +1 ;
        }    
            return min(alpha,beta);
    }
    else
    {
        int beta;
        if(v[i]==no)
            {
                 beta = recur(i+1,left,v,dp,no+1) ;
            }
        else
        {
             beta = recur(i+1,left,v,dp,no+1) +1 ;
        }
        return beta;
    }
}


signed main()
 {

    fasterio
    #ifndef ONLINE_JUDGE  
    freopen("error.txt", "w", stderr);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
int h,w;
cin>>h>>w;

vector<vector<char>> v(h,vector<char>(w));
deque<pair<int,int>> dq;
for(int i=0;i<h;i++)
{
    for(int j=0;j<w;j++)
    {
        cin>>v[i][j];
    }
}

vector<vector<int>> vis(h,vector<int>(w,0));

int ans =0;

char curr =v[0][0];

dq.push_back({0,0});

while (!dq.empty()) {
int a, b;
tie(a, b) = dq.front();
dq.pop_front();

if(v[a][b]!=curr){ curr= v[a][b]; ans+=1;}
vis[a][b]=1;

if(a-1>=0)
{
    if(v[a-1][b]!='.'&&vis[a-1][b]==0)
    {
        if(curr==v[a-1][b]) dq.push_front({a-1,b});
        else dq.push_back({a-1,b});
    }
}

if(a+1<h)
{
    if(v[a+1][b]!='.'&&vis[a+1][b]==0)
    {
        if(curr==v[a+1][b]) dq.push_front({a+1,b});
        else dq.push_back({a+1,b});
    }
}

if(b-1>=0)
{
    if(v[a][b-1]!='.'&&vis[a][b-1]==0)
    {
        if(curr==v[a][b-1]) dq.push_front({a,b-1});
        else dq.push_back({a,b-1});
    }
}

if(b+1<w)
{
    if(v[a][b+1]!='.'&&vis[a][b+1]==0)
    {
        if(curr==v[a][b+1]) dq.push_front({a,b+1});
        else dq.push_back({a,b+1});
    }
}

}

cout<<ans+1<<endl;


 }

Compilation message

tracks.cpp: In function 'long long int recur(long long int, long long int, std::vector<long long int>&, std::vector<std::vector<long long int> >&, long long int)':
tracks.cpp:50:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     if(i==v.size()) return 0;
      |        ~^~~~~~~~~~
tracks.cpp: In function 'int main()':
tracks.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen("error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 518 ms 227152 KB Output isn't correct
2 Incorrect 496 ms 226968 KB Output isn't correct
3 Incorrect 510 ms 228552 KB Output isn't correct
4 Incorrect 460 ms 228556 KB Output isn't correct
5 Incorrect 501 ms 228524 KB Output isn't correct
6 Incorrect 466 ms 227164 KB Output isn't correct
7 Incorrect 462 ms 228556 KB Output isn't correct
8 Incorrect 461 ms 228564 KB Output isn't correct
9 Incorrect 469 ms 228808 KB Output isn't correct
10 Incorrect 461 ms 226588 KB Output isn't correct
11 Incorrect 481 ms 227076 KB Output isn't correct
12 Incorrect 467 ms 227336 KB Output isn't correct
13 Incorrect 481 ms 227128 KB Output isn't correct
14 Incorrect 468 ms 228644 KB Output isn't correct
15 Incorrect 468 ms 226972 KB Output isn't correct
16 Incorrect 476 ms 228552 KB Output isn't correct
17 Incorrect 473 ms 228548 KB Output isn't correct
18 Incorrect 475 ms 226456 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 475 ms 227008 KB Output isn't correct
2 Incorrect 466 ms 226708 KB Output isn't correct
3 Incorrect 465 ms 226984 KB Output isn't correct
4 Incorrect 464 ms 226996 KB Output isn't correct
5 Incorrect 467 ms 228440 KB Output isn't correct
6 Incorrect 468 ms 228584 KB Output isn't correct
7 Incorrect 476 ms 228444 KB Output isn't correct
8 Incorrect 479 ms 226908 KB Output isn't correct
9 Incorrect 466 ms 226900 KB Output isn't correct
10 Incorrect 474 ms 226812 KB Output isn't correct
11 Incorrect 471 ms 228556 KB Output isn't correct
12 Incorrect 470 ms 228504 KB Output isn't correct
13 Incorrect 471 ms 228444 KB Output isn't correct
14 Incorrect 464 ms 227156 KB Output isn't correct
15 Incorrect 470 ms 226880 KB Output isn't correct
16 Incorrect 463 ms 228556 KB Output isn't correct
17 Incorrect 463 ms 226916 KB Output isn't correct
18 Incorrect 464 ms 228516 KB Output isn't correct
19 Incorrect 483 ms 228752 KB Output isn't correct
20 Incorrect 567 ms 228436 KB Output isn't correct
21 Incorrect 480 ms 228444 KB Output isn't correct
22 Incorrect 462 ms 226496 KB Output isn't correct
23 Incorrect 467 ms 226976 KB Output isn't correct
24 Incorrect 467 ms 228524 KB Output isn't correct
25 Incorrect 466 ms 226636 KB Output isn't correct
26 Incorrect 472 ms 228440 KB Output isn't correct
27 Incorrect 478 ms 228488 KB Output isn't correct
28 Incorrect 464 ms 226612 KB Output isn't correct
29 Incorrect 470 ms 226776 KB Output isn't correct
30 Incorrect 470 ms 226860 KB Output isn't correct
31 Incorrect 470 ms 228552 KB Output isn't correct
32 Incorrect 459 ms 228444 KB Output isn't correct