oj.uz

Submission #870687

# Submission time Handle Problem Language Result Execution time Memory
870687 2023-11-08T20:30:50 Z Servant_of_the_Lord Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 804 ms 54556 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1116 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 856 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 472 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 10 ms 892 KB Output is correct
16 Correct 11 ms 972 KB Output is correct
17 Correct 7 ms 860 KB Output is correct
18 Correct 8 ms 1372 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 39 ms 3844 KB Output is correct
3 Correct 200 ms 34140 KB Output is correct
4 Correct 47 ms 8476 KB Output is correct
5 Correct 157 ms 19764 KB Output is correct
6 Correct 804 ms 54460 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 2 ms 892 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 904 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 39 ms 3780 KB Output is correct
14 Correct 22 ms 2396 KB Output is correct
15 Correct 13 ms 2652 KB Output is correct
16 Correct 23 ms 1864 KB Output is correct
17 Correct 104 ms 9040 KB Output is correct
18 Correct 52 ms 8784 KB Output is correct
19 Correct 53 ms 8232 KB Output is correct
20 Correct 49 ms 7816 KB Output is correct
21 Correct 116 ms 20052 KB Output is correct
22 Correct 156 ms 19280 KB Output is correct
23 Correct 211 ms 16744 KB Output is correct
24 Correct 125 ms 19872 KB Output is correct
25 Correct 278 ms 34128 KB Output is correct
26 Correct 468 ms 26560 KB Output is correct
27 Correct 652 ms 37612 KB Output is correct
28 Correct 798 ms 54556 KB Output is correct
29 Correct 799 ms 51444 KB Output is correct
30 Correct 685 ms 49524 KB Output is correct
31 Correct 587 ms 22976 KB Output is correct
32 Correct 562 ms 35408 KB Output is correct