oj.uz

Submission #346396

# Submission time Handle Problem Language Result Execution time Memory
346396 2021-01-09T14:12:18 Z jenishmonpara Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 903 ms 305028 KB 
#include <bits/stdc++.h>
using namespace std;
long double PI = acos(-1);
long double DEL = 1e-10;
int M =  1e9 + 7;
const int N = 3e5 + 10;

#define ftt cin>>t;for(int tt=1;tt<=t;++tt)
#define all(a) a.begin(),a.end()
#define vpii vector<pair<int,int>>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vi vector<int>
#define sq(a) ((a)*(a))
#define double long double
#define dbg cout<<"\nhi\n";
#define int long long
#define nl cout<<"\n"
#define sp <<" "<<
#define S second
#define F first

int fpow(int x, int n)
{
      int res = 1;
      x %= M;
      while(n)
      {
            if(n&1)res = res * x % M;
            x = x * x % M;
            n>>=1;
      }
      return res;
}
int gcd(int a,int b)
{
      if(b == 0)return a;
      return gcd(b,a % b);
}
int lcm(int a,int b)
{
      return a*(b/gcd(a,b));
}
void create_fac(int n)
{
      vector<int> fac(N),inv(N);
      fac[0] = inv[0] = 1;
      for(int i=1;i<=n;i++)
      {
            fac[i] = fac[i-1]*i % M;
            inv[i] = fpow(fac[i],M-2);
      }
}
int ncr(int n,int r)
{
      vector<int> fac(N),inv(N);
      return fac[n] * (inv[r] * inv[n-r] % M) % M;
      return fac[n] * (fpow(fac[r],M-2) * fpow(fac[n-r],M-2) % M ) % M;
}
void sieve (int n)      // linear sieve
{
      vector <int> primes;
      bool iscomp[N];
      for (int i = 2; i <= n; ++i)
      {
            if (!iscomp[i]) primes.push_back(i);
            for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
            {
                  iscomp[i * primes[j]] = true;
                  if (i % primes[j] == 0) break;
            }
      }
}

// you can also use __int128
// priority_queue<int,vector<int>,greater<int>>
// bitset<100>(x).count()
//**************************************** CHECK CONSTRAINTS ***********************************************
int cnt, sum, mid, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z;
string s;


int32_t main()
{
      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      cin >> n >> m;
      vvi a(n+2,vi(m+2)),dis(n+2,vi(m+2));
      for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
      {
            char c;
            cin>>c;
            if(c == '.')
            {
                  a[i][j] = 0;
            }
            else if(c == 'F')
            {
                  a[i][j] = 2;
            }
            else
            {
                  a[i][j] = 1;
            }
      }
      dis[1][1] = 1;
      deque<pii> q;
      q.push_back({1,1});
      while(!q.empty())
      {
            int i = q.front().F,j = q.front().S;
            q.pop_front();
            ans = max(ans,dis[i][j]);
            if(!dis[i-1][j] and a[i-1][j])
            {

                  if(a[i-1][j]!=a[i][j])
                  {
                        dis[i-1][j] = dis[i][j] + 1;
                        q.push_back({i-1,j});
                  }
                  else
                  {
                        dis[i-1][j] = dis[i][j];
                        q.push_front({i-1,j});

                  }
            }
            if(!dis[i+1][j] and a[i+1][j])
            {
                  if(a[i+1][j]!=a[i][j])
                  {
                        dis[i+1][j] = dis[i][j] + 1;
                        q.push_back({i+1,j});

                  }
                  else
                  {
                        dis[i+1][j] = dis[i][j];
                        q.push_front({i+1,j});

                  }
            }
            //cout<<dis[i][j+1] sp a[i][j+1];nl;
            if(!dis[i][j+1] and a[i][j+1])
            {
                  
                  if(a[i][j+1]!=a[i][j])
                  {
                        dis[i][j+1] = dis[i][j] + 1;
                        q.push_back({i,j+1});
                  }
                  else
                  {
                        dis[i][j+1] = dis[i][j];
                        q.push_front({i,j+1});
                  }
            }
            if(!dis[i][j-1] and a[i][j-1])
            {
                  
                  if(a[i][j-1]!=a[i][j])
                  {
                        dis[i][j-1] = dis[i][j] + 1;
                        q.push_back({i,j-1});
                  }
                  else
                  {
                        dis[i][j-1] = dis[i][j];
                        q.push_front({i,j-1});
                  }
            }
            
      }
      cout<<ans;
}
/*
 5 8
 FFR.....
 .FRRR...
 .FFFFF..
 ..RRRFFR
 .....FFF
 */

Compilation message

tracks.cpp: In function 'void sieve(long long int)':
tracks.cpp:67:31: 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]
   67 |             for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4588 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 9 ms 3364 KB Output is correct
5 Correct 4 ms 1772 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 3 ms 1516 KB Output is correct
11 Correct 3 ms 1132 KB Output is correct
12 Correct 6 ms 1900 KB Output is correct
13 Correct 4 ms 1772 KB Output is correct
14 Correct 4 ms 1772 KB Output is correct
15 Correct 13 ms 4588 KB Output is correct
16 Correct 15 ms 4588 KB Output is correct
17 Correct 13 ms 4460 KB Output is correct
18 Correct 8 ms 3436 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1516 KB Output is correct
2 Correct 72 ms 26604 KB Output is correct
3 Correct 538 ms 267180 KB Output is correct
4 Correct 156 ms 62956 KB Output is correct
5 Correct 309 ms 150612 KB Output is correct
6 Correct 903 ms 295744 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 3 ms 1516 KB Output is correct
9 Correct 3 ms 1516 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 3 ms 1516 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 71 ms 26604 KB Output is correct
14 Correct 48 ms 15468 KB Output is correct
15 Correct 41 ms 17004 KB Output is correct
16 Correct 30 ms 11116 KB Output is correct
17 Correct 188 ms 68204 KB Output is correct
18 Correct 168 ms 67180 KB Output is correct
19 Correct 157 ms 62956 KB Output is correct
20 Correct 118 ms 57836 KB Output is correct
21 Correct 310 ms 155756 KB Output is correct
22 Correct 307 ms 150488 KB Output is correct
23 Correct 367 ms 129584 KB Output is correct
24 Correct 305 ms 152044 KB Output is correct
25 Correct 788 ms 267116 KB Output is correct
26 Correct 590 ms 305028 KB Output is correct
27 Correct 757 ms 294088 KB Output is correct
28 Correct 900 ms 295772 KB Output is correct
29 Correct 887 ms 291960 KB Output is correct
30 Correct 817 ms 292624 KB Output is correct
31 Correct 747 ms 172268 KB Output is correct
32 Correct 712 ms 296236 KB Output is correct