oj.uz

Submission #956613

# Submission time Handle Problem Language Result Execution time Memory
956613 2024-04-02T08:27:36 Z Kladness Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1071 ms 321340 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 ='x';

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;
      |        ~^~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3164 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 10 ms 2908 KB Output isn't correct
5 Incorrect 3 ms 1236 KB Output isn't correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Incorrect 3 ms 1116 KB Output isn't correct
11 Incorrect 3 ms 1116 KB Output isn't correct
12 Incorrect 6 ms 1412 KB Output isn't correct
13 Incorrect 3 ms 1116 KB Output isn't correct
14 Incorrect 2 ms 1236 KB Output isn't correct
15 Incorrect 17 ms 2908 KB Output isn't correct
16 Incorrect 15 ms 3160 KB Output isn't correct
17 Incorrect 9 ms 2652 KB Output isn't correct
18 Incorrect 10 ms 2952 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1112 KB Output isn't correct
2 Incorrect 51 ms 15708 KB Output isn't correct
3 Incorrect 325 ms 157160 KB Output isn't correct
4 Incorrect 91 ms 37256 KB Output isn't correct
5 Incorrect 177 ms 88672 KB Output isn't correct
6 Incorrect 1071 ms 224924 KB Output isn't correct
7 Incorrect 2 ms 1116 KB Output isn't correct
8 Incorrect 2 ms 1116 KB Output isn't correct
9 Incorrect 2 ms 1116 KB Output isn't correct
10 Incorrect 1 ms 728 KB Output isn't correct
11 Incorrect 2 ms 1112 KB Output isn't correct
12 Incorrect 1 ms 604 KB Output isn't correct
13 Incorrect 64 ms 15840 KB Output isn't correct
14 Incorrect 29 ms 9308 KB Output isn't correct
15 Incorrect 19 ms 10072 KB Output isn't correct
16 Incorrect 32 ms 6584 KB Output isn't correct
17 Incorrect 126 ms 40276 KB Output isn't correct
18 Incorrect 87 ms 39504 KB Output isn't correct
19 Incorrect 97 ms 37060 KB Output isn't correct
20 Incorrect 73 ms 34228 KB Output isn't correct
21 Incorrect 221 ms 91732 KB Output isn't correct
22 Incorrect 183 ms 88680 KB Output isn't correct
23 Incorrect 253 ms 76468 KB Output isn't correct
24 Incorrect 201 ms 89416 KB Output isn't correct
25 Incorrect 600 ms 157160 KB Output isn't correct
26 Incorrect 694 ms 321340 KB Output isn't correct
27 Incorrect 833 ms 210268 KB Output isn't correct
28 Incorrect 1025 ms 225164 KB Output isn't correct
29 Incorrect 1025 ms 218100 KB Output isn't correct
30 Incorrect 924 ms 227328 KB Output isn't correct
31 Incorrect 683 ms 103116 KB Output isn't correct
32 Incorrect 736 ms 219924 KB Output isn't correct