oj.uz

Submission #956610

# Submission time Handle Problem Language Result Execution time Memory
956610 2024-04-02T08:27:07 Z Kladness Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 502 ms 228824 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;
      |        ~^~~~~~~~~~
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 467 ms 226984 KB Output isn't correct
2 Incorrect 466 ms 226644 KB Output isn't correct
3 Incorrect 461 ms 226744 KB Output isn't correct
4 Incorrect 457 ms 228548 KB Output isn't correct
5 Incorrect 468 ms 226720 KB Output isn't correct
6 Incorrect 465 ms 227220 KB Output isn't correct
7 Incorrect 463 ms 228556 KB Output isn't correct
8 Incorrect 461 ms 228312 KB Output isn't correct
9 Incorrect 466 ms 227020 KB Output isn't correct
10 Incorrect 457 ms 226928 KB Output isn't correct
11 Incorrect 461 ms 227240 KB Output isn't correct
12 Incorrect 458 ms 226904 KB Output isn't correct
13 Incorrect 455 ms 228760 KB Output isn't correct
14 Incorrect 459 ms 226648 KB Output isn't correct
15 Incorrect 461 ms 226980 KB Output isn't correct
16 Incorrect 459 ms 227116 KB Output isn't correct
17 Incorrect 460 ms 228552 KB Output isn't correct
18 Incorrect 459 ms 228824 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 227152 KB Output isn't correct
2 Incorrect 455 ms 226900 KB Output isn't correct
3 Incorrect 461 ms 228700 KB Output isn't correct
4 Incorrect 470 ms 226692 KB Output isn't correct
5 Incorrect 456 ms 228328 KB Output isn't correct
6 Incorrect 458 ms 228328 KB Output isn't correct
7 Incorrect 458 ms 226944 KB Output isn't correct
8 Incorrect 483 ms 228552 KB Output isn't correct
9 Incorrect 472 ms 226900 KB Output isn't correct
10 Incorrect 478 ms 226512 KB Output isn't correct
11 Incorrect 475 ms 226868 KB Output isn't correct
12 Incorrect 472 ms 228308 KB Output isn't correct
13 Incorrect 485 ms 226732 KB Output isn't correct
14 Incorrect 474 ms 226548 KB Output isn't correct
15 Incorrect 481 ms 227076 KB Output isn't correct
16 Incorrect 502 ms 228500 KB Output isn't correct
17 Incorrect 477 ms 226952 KB Output isn't correct
18 Incorrect 483 ms 226980 KB Output isn't correct
19 Incorrect 471 ms 228440 KB Output isn't correct
20 Incorrect 482 ms 228516 KB Output isn't correct
21 Incorrect 467 ms 228444 KB Output isn't correct
22 Incorrect 485 ms 226624 KB Output isn't correct
23 Incorrect 474 ms 226584 KB Output isn't correct
24 Incorrect 473 ms 226600 KB Output isn't correct
25 Incorrect 499 ms 228804 KB Output isn't correct
26 Incorrect 466 ms 226672 KB Output isn't correct
27 Incorrect 469 ms 228560 KB Output isn't correct
28 Incorrect 479 ms 226988 KB Output isn't correct
29 Incorrect 483 ms 228520 KB Output isn't correct
30 Incorrect 476 ms 228556 KB Output isn't correct
31 Incorrect 487 ms 226564 KB Output isn't correct
32 Incorrect 488 ms 228412 KB Output isn't correct