Submission #1120959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120959		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	1246 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ld double


const int INF = 1e18;
const int mod = 12345;
const int sz = 4e3 + 109;

int n , m , ans = 1;
char a[sz][sz];
bool vis[sz][sz];

int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};

bool can_go(int x , int y)
{
    if(x >= 1 && y >= 1 && n >= x && m >= y) return true;
    else return false;
}

void dfs(int x , int y , vector < pair < int , int > > &q)
{
    vis[x][y] = 1;
    for(int p = 0;p < 4;p++)
    {
        int i = x + dx[p];
        int j = y + dy[p];
        if(!i or !j or i > n or j > m) continue;
        if(vis[i][j]) continue;
        if(a[i][j] == '.') continue;
        if(a[x][y] != a[i][j]) q.push_back({i,j});
        else dfs(i , j , q);
    }
}

int main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);
   cin >> n >> m;
   for(int i = 1;i <= n;i++)
   {
       for(int j = 1;j <= m;j++)
       {
           cin >> a[i][j];
       }
   }
   vector < pair < int , int > > q;
   vector < pair < int , int > > q2;
   dfs(1 , 1 , q);
   while(!q.empty())
   {
       ans++;
       q2.clear();
       while(!q.empty())
       {
           int x = q[q.size() - 1].first , y = q[q.size() - 1].second;
           q.pop_back();
           dfs(x , y , q2);
       }
       q = q2;
   }
   cout << ans << endl;
}

Compilation message (stderr)

tracks.cpp:7:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int INF = 1e18;
      |                 ^~~~

• Subtask 1: 30 / 30
• Subtask 2: 67.8125 / 70