제출 #346396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346396		jenishmonpara	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	903 ms	305028 KiB

tracks

#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
 */

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 70 / 70