Submission #870687

#	Time	Username	Problem	Language	Result	Execution time	Memory
870687		Servant_of_the_Lord	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	804 ms	54556 KiB

tracks

#include <bits/stdc++.h>
#define ll long long

using namespace std;

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    ll x,y,z,a,b,c;
    cin>>x>>y;
    vector<string>v;
    vector<vector<bool>>w;
    for(ll i=0;i<x;i++)w.push_back(vector<bool>(y));
    for(ll i=0;i<x;i++)
    {
        string s;
        cin>>s;
        v.push_back(s);
    }
    queue<pair<ll,ll>>q,r;
    q.push({0,0});
    a=0;
    function<void(ll,ll,ll,ll)>add=[&](ll a,ll b,ll c,ll d)
    {
        if(a>=0&&a<x&&b>=0&&b<y&&!w[a][b])
        {
            w[a][b]=true;
            if(v[a][b]==v[c][d])q.push({a,b});
            else if(v[a][b]!='.')r.push({a,b});
        }
    };
    while(q.size())
    {
        a++;
        while(q.size())
        {
            pair<ll,ll>p=q.front();
            add(p.first-1,p.second,p.first,p.second);
            add(p.first+1,p.second,p.first,p.second);
            add(p.first,p.second-1,p.first,p.second);
            add(p.first,p.second+1,p.first,p.second);
            q.pop();
        }
        q.swap(r);
    }
    cout<<a<<'\n';
}

Compilation message (stderr)

tracks.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main()
      | ^~~~
tracks.cpp: In function 'int main()':
tracks.cpp:11:12: warning: unused variable 'z' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c;
      |            ^
tracks.cpp:11:16: warning: unused variable 'b' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c;
      |                ^
tracks.cpp:11:18: warning: unused variable 'c' [-Wunused-variable]
   11 |     ll x,y,z,a,b,c;
      |                  ^

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