Submission #535392

#	Time	Username	Problem	Language	Result	Execution time	Memory
535392		Karabasan	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1581 ms	120688 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define fast1 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
//#define int long long
#define mod 1000000007
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,avx")
//#pragma GCC optimize("unroll-loops")

int n,m;
char dizi[4003][4003];
int vis[4003][4003];
queue<pair<pair<int,int> ,int> > q;
queue<pair<pair<int,int>,int> > q1;
void dfs(int x,int y,char z)
{
    if(vis[x][y])
        return;
    vis[x][y]=1;
    if(!vis[x+1][y]&&dizi[x+1][y]==z)
        dfs(x+1,y,z);
    if(!vis[x-1][y]&&dizi[x-1][y]==z)
        dfs(x-1,y,z);
    if(!vis[x][y+1]&&dizi[x][y+1]==z)
        dfs(x,y+1,z);
    if(!vis[x][y-1]&&dizi[x][y-1]==z)
        dfs(x,y-1,z);
    /////////////////////////////////////
    if(!vis[x+1][y]&&dizi[x+1][y]!=z&&dizi[x+1][y]!='.')
        q.push({{x+1,y},2});
    if(!vis[x-1][y]&&dizi[x-1][y]!=z&&dizi[x-1][y]!='.')
        q.push({{x-1,y},2});
    if(!vis[x][y+1]&&dizi[x][y+1]!=z&&dizi[x][y+1]!='.')
        q.push({{x,y+1},2});
    if(!vis[x][y-1]&&dizi[x][y-1]!=z&&dizi[x][y-1]!='.')
        q.push({{x,y-1},2});
}
void solve()
{
    cin>>n>>m;
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++)
            dizi[i][j]='.';
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>dizi[i][j];
    /*dfs(1,1,dizi[1][1]);
    if(q.empty())
    {
        cout<<1;
        return;
    }
    */
    int mx=1;
    q.push({{1,1},1});
    while(1)
    {
        if(q.size()==0)
        {
            cout<<mx;
            return;
        }
        while(!q.empty())
        {
            int x=q.front().first.first;
            int y=q.front().first.second;
            int z=q.front().second;
            q.pop();
            if(vis[x][y])
                continue;
            vis[x][y]=1;
            mx=max(mx,z);
            if(!vis[x+1][y]&&dizi[x+1][y]==dizi[x][y])
                q.push({{x+1,y},z});
            if(!vis[x-1][y]&&dizi[x-1][y]==dizi[x][y])
                q.push({{x-1,y},z});
            if(!vis[x][y+1]&&dizi[x][y+1]==dizi[x][y])
                q.push({{x,y+1},z});
            if(!vis[x][y-1]&&dizi[x][y-1]==dizi[x][y])
                q.push({{x,y-1},z});
            /////////////////////////////
            if(!vis[x+1][y]&&dizi[x+1][y]!=dizi[x][y]&&dizi[x+1][y]!='.')
                q1.push({{x+1,y},z+1});
            if(!vis[x-1][y]&&dizi[x-1][y]!=dizi[x][y]&&dizi[x-1][y]!='.')
                q1.push({{x-1,y},z+1});
            if(!vis[x][y+1]&&dizi[x][y+1]!=dizi[x][y]&&dizi[x][y+1]!='.')
                q1.push({{x,y+1},z+1});
            if(!vis[x][y-1]&&dizi[x][y-1]!=dizi[x][y]&&dizi[x][y-1]!='.')
                q1.push({{x,y-1},z+1});
        }
        while(!q1.empty())
        {
            int x=q1.front().first.first;
            int y=q1.front().first.second;
            int z=q1.front().second;
            q1.pop();
            if(vis[x][y])
                continue;
            vis[x][y]=1;
            mx=max(mx,z);
            if(!vis[x+1][y]&&dizi[x+1][y]==dizi[x][y])
                q1.push({{x+1,y},z});
            if(!vis[x-1][y]&&dizi[x-1][y]==dizi[x][y])
                q1.push({{x-1,y},z});
            if(!vis[x][y+1]&&dizi[x][y+1]==dizi[x][y])
                q1.push({{x,y+1},z});
            if(!vis[x][y-1]&&dizi[x][y-1]==dizi[x][y])
                q1.push({{x,y-1},z});
            /////////////////////////////
            if(!vis[x+1][y]&&dizi[x+1][y]!=dizi[x][y]&&dizi[x+1][y]!='.')
                q.push({{x+1,y},z+1});
            if(!vis[x-1][y]&&dizi[x-1][y]!=dizi[x][y]&&dizi[x-1][y]!='.')
                q.push({{x-1,y},z+1});
            if(!vis[x][y+1]&&dizi[x][y+1]!=dizi[x][y]&&dizi[x][y+1]!='.')
                q.push({{x,y+1},z+1});
            if(!vis[x][y-1]&&dizi[x][y-1]!=dizi[x][y]&&dizi[x][y-1]!='.')
                q.push({{x,y-1},z+1});
        }
        if(q.size()==0)
        {
            cout<<mx;
            return;
        }
    }
}
signed main()
{
    //freopen ("lca.gir","r",stdin);
    //freopen ("lca.cik","w",stdout);
    fast1
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

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