oj.uz

Submission #888233

# Submission time Handle Problem Language Result Execution time Memory
888233 2023-12-16T15:07:53 Z ace5 Maze (JOI23_ho_t3) C++17
35 / 100
 812 ms 582052 KB 
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int maxr = 3001;
const int maxc = 6000001;

set<short> r[maxr];
set<short> c[maxc];
vector<short> vis[maxr];
vector<int> d[maxr];
vector<bool> a[maxr];
deque<pair<int,int>> f;

int R,C,n;

int bfs(int si,int sj,int fi,int fj)
{
    for(int i = 0;i < R;++i)
    {
        d[i].resize(C);
        vis[i].resize(C);
        for(int j = 0;j < C;++j)
        {
            d[i][j] = INF;
            vis[i][j] = 0;
            if(i != si || j != sj)
            {
                r[i].insert(j);
                c[j].insert(i);

            }
        }
    }
    d[si][sj] = 0;
    vis[si][sj] = 2;
    f.push_back({si,sj});
    while(f.size())
    {
        int i = f[0].first;
        int j = f[0].second;
        f.pop_front();
       // cout << i << ' ' << j << ' ' << d[fi][fj] << ' ' << vis[5][0] << "\n";
        if(vis[i][j] == 3)
            continue;
        vis[i][j] = 3;
        if(i == fi && j == fj)
            break;
        if(i > 0 && a[i-1][j] == 0 && vis[i-1][j] < 2)
        {
            if(!vis[i-1][j])
            {
                r[i-1].erase(j);
                c[j].erase(i-1);
            }
            vis[i-1][j] = 2;
            d[i-1][j] = d[i][j];
            f.push_front({i-1,j});
        }
        if(j > 0 && a[i][j-1] == 0 && vis[i][j-1] < 2)
        {
            if(!vis[i][j-1])
            {
                r[i].erase(j-1);
                c[j-1].erase(i);
            }
          //  if(i == 5 && j == 1)
         //   {
          //      cout << d[i][j] << ' ' << d[i][j-1] << "\n";
          //  }
            vis[i][j-1] = 2;
            d[i][j-1] = d[i][j];
            f.push_front({i,j-1});
        }
        if(i < R-1 && a[i+1][j] == 0 && vis[i+1][j] < 2)
        {
            if(!vis[i+1][j])
            {
                r[i+1].erase(j);
                c[j].erase(i+1);
            }
            vis[i+1][j] = 2;
            d[i+1][j] = d[i][j];
            f.push_front({i+1,j});
        }
        if(j < C-1 && a[i][j+1] == 0 && vis[i][j+1] < 2)
        {
            if(!vis[i][j+1])
            {
                r[i].erase(j+1);
                c[j+1].erase(i);
            }
            vis[i][j+1] = 2;
            d[i][j+1] = d[i][j];
            f.push_front({i,j+1});
        }
        if(abs(i-fi) <= n && abs(j-fj) <= n && !vis[fi][fj])
        {
            r[fi].erase(fj);
            c[fj].erase(fi);
            //cout << i << ' ' << j << ' ' << d[i][j] << "!\n";
            vis[fi][fj] = 1;
            d[fi][fj] = d[i][j]+1;
            f.push_back({fi,fj});
        }
        int indd = min(R-1,i+n);
        int indu = max(0,i-n);
        int indl = max(0,j-n);
        int indr = min(C-1,j+n);
        int indd2 = i+n-1;
        int indu2 = i-n+1;
        int indr2 = j+n-1;
        int indl2 = j-n+1;
        for(;;)
        {
            auto it = r[indd].lower_bound(indl2);
            if(it != r[indd].end() && (*it) <= indr2)
            {
                int k = (*it);
                vis[indd][k] = 1;
                //cout << indd << ' ' << k << ' ' << d[i][j] << "!\n";
                d[indd][k] = d[i][j]+1;
                //cout << d[1][0] << ' ';
                f.push_back({indd,k});
                r[indd].erase(it);
                c[(*it)].erase(indd);
            }
            else
                break;
        }
        for(;;)
        {
            auto it = r[indu].lower_bound(indl2);
            if(it != r[indu].end() && (*it) <= indr2)
            {
                int k = (*it);
                vis[indu][k] = 1;
                d[indu][k] = d[i][j]+1;
                //cout << indu << ' ' << k << "!!\n";
                f.push_back({indu,k});
                r[indu].erase(it);
                c[(*it)].erase(indu);
            }
            else
                break;
        }
        for(;;)
        {
            auto it = c[indl].lower_bound(indu2);
            if(it != c[indl].end() && (*it) <= indd2)
            {
                int k = (*it);
                vis[k][indl] = 1;
                d[k][indl] = d[i][j]+1;
                //cout << k << ' ' << indl << "!!!\n";
                f.push_back({k,indl});
                c[indl].erase(it);
                r[(*it)].erase(indl);
            }
            else
                break;
        }
        for(;;)
        {
            auto it = c[indr].lower_bound(indu2);
            if(it != c[indr].end() && (*it) <= indd2)
            {
                int k = (*it);
                vis[k][indr] = 1;
                d[k][indr] = d[i][j]+1;
                //cout << k << ' ' << indr << "!!!!\n";
                f.push_back({k,indr});
                c[indr].erase(it);
                r[(*it)].erase(indr);
            }
            else
                break;
        }
    }
    return d[fi][fj];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C >> n;
    int si,sj,fi,fj;
    cin >> si >> sj >> fi >> fj;
    si--;
    sj--;
    fi--;
    fj--;
    for(int i = 0;i < R;++i)
    {
        string s;
        cin >> s;
        a[i].resize(C);
        for(int j =0;j < C;++j)
        {
            a[i][j] = (s[j] == '.' ? 0 : 1);
        }
    }
    cout << bfs(si,sj,fi,fj);
    return 0;

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 282468 KB Output is correct
2 Correct 56 ms 282452 KB Output is correct
3 Correct 58 ms 282712 KB Output is correct
4 Correct 54 ms 282704 KB Output is correct
5 Correct 54 ms 282728 KB Output is correct
6 Correct 54 ms 282700 KB Output is correct
7 Correct 54 ms 282732 KB Output is correct
8 Correct 57 ms 282552 KB Output is correct
9 Correct 55 ms 282448 KB Output is correct
10 Correct 54 ms 282540 KB Output is correct
11 Correct 53 ms 282444 KB Output is correct
12 Correct 54 ms 282444 KB Output is correct
13 Correct 55 ms 282640 KB Output is correct
14 Correct 54 ms 282448 KB Output is correct
15 Correct 54 ms 282448 KB Output is correct
16 Correct 54 ms 282704 KB Output is correct
17 Correct 55 ms 282644 KB Output is correct
18 Correct 56 ms 282732 KB Output is correct
19 Correct 76 ms 288592 KB Output is correct
20 Runtime error 274 ms 582048 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 282456 KB Output is correct
2 Correct 55 ms 282628 KB Output is correct
3 Correct 55 ms 282628 KB Output is correct
4 Correct 53 ms 282448 KB Output is correct
5 Correct 54 ms 282708 KB Output is correct
6 Correct 54 ms 282436 KB Output is correct
7 Correct 54 ms 282640 KB Output is correct
8 Correct 56 ms 282448 KB Output is correct
9 Correct 55 ms 282704 KB Output is correct
10 Correct 55 ms 282704 KB Output is correct
11 Correct 54 ms 282724 KB Output is correct
12 Correct 57 ms 282720 KB Output is correct
13 Correct 54 ms 282964 KB Output is correct
14 Correct 54 ms 282708 KB Output is correct
15 Correct 54 ms 282708 KB Output is correct
16 Correct 54 ms 282712 KB Output is correct
17 Correct 54 ms 282708 KB Output is correct
18 Correct 53 ms 282448 KB Output is correct
19 Correct 54 ms 282708 KB Output is correct
20 Correct 53 ms 282656 KB Output is correct
21 Correct 55 ms 282452 KB Output is correct
22 Correct 54 ms 282556 KB Output is correct
23 Correct 54 ms 282452 KB Output is correct
24 Correct 55 ms 282452 KB Output is correct
25 Correct 56 ms 282624 KB Output is correct
26 Correct 55 ms 282564 KB Output is correct
27 Correct 55 ms 282648 KB Output is correct
28 Correct 55 ms 282700 KB Output is correct
29 Correct 55 ms 282632 KB Output is correct
30 Correct 55 ms 282704 KB Output is correct
31 Correct 55 ms 282504 KB Output is correct
32 Correct 54 ms 282716 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 282448 KB Output is correct
2 Correct 54 ms 282444 KB Output is correct
3 Correct 54 ms 282416 KB Output is correct
4 Correct 54 ms 282452 KB Output is correct
5 Correct 57 ms 282628 KB Output is correct
6 Correct 54 ms 282412 KB Output is correct
7 Correct 54 ms 282708 KB Output is correct
8 Correct 54 ms 282712 KB Output is correct
9 Correct 55 ms 282704 KB Output is correct
10 Correct 54 ms 282708 KB Output is correct
11 Correct 55 ms 282668 KB Output is correct
12 Correct 55 ms 282708 KB Output is correct
13 Correct 53 ms 282448 KB Output is correct
14 Correct 53 ms 282564 KB Output is correct
15 Correct 54 ms 282448 KB Output is correct
16 Correct 54 ms 282652 KB Output is correct
17 Correct 56 ms 282452 KB Output is correct
18 Correct 54 ms 282616 KB Output is correct
19 Correct 53 ms 282400 KB Output is correct
20 Correct 53 ms 282648 KB Output is correct
21 Correct 58 ms 282708 KB Output is correct
22 Correct 54 ms 282660 KB Output is correct
23 Correct 56 ms 282708 KB Output is correct
24 Correct 56 ms 282708 KB Output is correct
25 Correct 63 ms 286432 KB Output is correct
26 Correct 68 ms 287936 KB Output is correct
27 Correct 74 ms 288588 KB Output is correct
28 Correct 71 ms 288592 KB Output is correct
29 Correct 72 ms 288592 KB Output is correct
30 Correct 71 ms 288504 KB Output is correct
31 Correct 72 ms 288660 KB Output is correct
32 Correct 72 ms 288508 KB Output is correct
33 Correct 72 ms 288492 KB Output is correct
34 Correct 93 ms 294480 KB Output is correct
35 Correct 102 ms 297552 KB Output is correct
36 Correct 113 ms 297864 KB Output is correct
37 Correct 102 ms 297500 KB Output is correct
38 Correct 101 ms 297584 KB Output is correct
39 Correct 222 ms 326108 KB Output is correct
40 Correct 626 ms 409652 KB Output is correct
41 Correct 659 ms 432544 KB Output is correct
42 Correct 660 ms 432680 KB Output is correct
43 Correct 583 ms 432468 KB Output is correct
44 Correct 565 ms 432584 KB Output is correct
45 Correct 779 ms 432668 KB Output is correct
46 Correct 812 ms 432456 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 282456 KB Output is correct
2 Correct 55 ms 282628 KB Output is correct
3 Correct 55 ms 282628 KB Output is correct
4 Correct 53 ms 282448 KB Output is correct
5 Correct 54 ms 282708 KB Output is correct
6 Correct 54 ms 282436 KB Output is correct
7 Correct 54 ms 282640 KB Output is correct
8 Correct 56 ms 282448 KB Output is correct
9 Correct 55 ms 282704 KB Output is correct
10 Correct 55 ms 282704 KB Output is correct
11 Correct 54 ms 282724 KB Output is correct
12 Correct 57 ms 282720 KB Output is correct
13 Correct 54 ms 282964 KB Output is correct
14 Correct 54 ms 282708 KB Output is correct
15 Correct 54 ms 282708 KB Output is correct
16 Correct 54 ms 282712 KB Output is correct
17 Correct 54 ms 282708 KB Output is correct
18 Correct 53 ms 282448 KB Output is correct
19 Correct 54 ms 282708 KB Output is correct
20 Correct 53 ms 282656 KB Output is correct
21 Correct 55 ms 282452 KB Output is correct
22 Correct 54 ms 282556 KB Output is correct
23 Correct 54 ms 282452 KB Output is correct
24 Correct 55 ms 282452 KB Output is correct
25 Correct 56 ms 282624 KB Output is correct
26 Correct 55 ms 282564 KB Output is correct
27 Correct 55 ms 282648 KB Output is correct
28 Correct 55 ms 282700 KB Output is correct
29 Correct 55 ms 282632 KB Output is correct
30 Correct 55 ms 282704 KB Output is correct
31 Correct 55 ms 282504 KB Output is correct
32 Correct 54 ms 282716 KB Output is correct
33 Correct 76 ms 288596 KB Output is correct
34 Correct 56 ms 282804 KB Output is correct
35 Correct 55 ms 282960 KB Output is correct
36 Correct 68 ms 286344 KB Output is correct
37 Runtime error 273 ms 582052 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 282456 KB Output is correct
2 Correct 55 ms 282628 KB Output is correct
3 Correct 55 ms 282628 KB Output is correct
4 Correct 53 ms 282448 KB Output is correct
5 Correct 54 ms 282708 KB Output is correct
6 Correct 54 ms 282436 KB Output is correct
7 Correct 54 ms 282640 KB Output is correct
8 Correct 56 ms 282448 KB Output is correct
9 Correct 55 ms 282704 KB Output is correct
10 Correct 55 ms 282704 KB Output is correct
11 Correct 54 ms 282724 KB Output is correct
12 Correct 57 ms 282720 KB Output is correct
13 Correct 54 ms 282964 KB Output is correct
14 Correct 54 ms 282708 KB Output is correct
15 Correct 54 ms 282708 KB Output is correct
16 Correct 54 ms 282712 KB Output is correct
17 Correct 54 ms 282708 KB Output is correct
18 Correct 53 ms 282448 KB Output is correct
19 Correct 54 ms 282708 KB Output is correct
20 Correct 53 ms 282656 KB Output is correct
21 Correct 55 ms 282452 KB Output is correct
22 Correct 54 ms 282556 KB Output is correct
23 Correct 54 ms 282452 KB Output is correct
24 Correct 55 ms 282452 KB Output is correct
25 Correct 56 ms 282624 KB Output is correct
26 Correct 55 ms 282564 KB Output is correct
27 Correct 55 ms 282648 KB Output is correct
28 Correct 55 ms 282700 KB Output is correct
29 Correct 55 ms 282632 KB Output is correct
30 Correct 55 ms 282704 KB Output is correct
31 Correct 55 ms 282504 KB Output is correct
32 Correct 54 ms 282716 KB Output is correct
33 Correct 76 ms 288596 KB Output is correct
34 Correct 56 ms 282804 KB Output is correct
35 Correct 55 ms 282960 KB Output is correct
36 Correct 68 ms 286344 KB Output is correct
37 Runtime error 273 ms 582052 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 282468 KB Output is correct
2 Correct 56 ms 282452 KB Output is correct
3 Correct 58 ms 282712 KB Output is correct
4 Correct 54 ms 282704 KB Output is correct
5 Correct 54 ms 282728 KB Output is correct
6 Correct 54 ms 282700 KB Output is correct
7 Correct 54 ms 282732 KB Output is correct
8 Correct 57 ms 282552 KB Output is correct
9 Correct 55 ms 282448 KB Output is correct
10 Correct 54 ms 282540 KB Output is correct
11 Correct 53 ms 282444 KB Output is correct
12 Correct 54 ms 282444 KB Output is correct
13 Correct 55 ms 282640 KB Output is correct
14 Correct 54 ms 282448 KB Output is correct
15 Correct 54 ms 282448 KB Output is correct
16 Correct 54 ms 282704 KB Output is correct
17 Correct 55 ms 282644 KB Output is correct
18 Correct 56 ms 282732 KB Output is correct
19 Correct 76 ms 288592 KB Output is correct
20 Runtime error 274 ms 582048 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 282468 KB Output is correct
2 Correct 56 ms 282452 KB Output is correct
3 Correct 58 ms 282712 KB Output is correct
4 Correct 54 ms 282704 KB Output is correct
5 Correct 54 ms 282728 KB Output is correct
6 Correct 54 ms 282700 KB Output is correct
7 Correct 54 ms 282732 KB Output is correct
8 Correct 57 ms 282552 KB Output is correct
9 Correct 55 ms 282448 KB Output is correct
10 Correct 54 ms 282540 KB Output is correct
11 Correct 53 ms 282444 KB Output is correct
12 Correct 54 ms 282444 KB Output is correct
13 Correct 55 ms 282640 KB Output is correct
14 Correct 54 ms 282448 KB Output is correct
15 Correct 54 ms 282448 KB Output is correct
16 Correct 54 ms 282704 KB Output is correct
17 Correct 55 ms 282644 KB Output is correct
18 Correct 56 ms 282732 KB Output is correct
19 Correct 76 ms 288592 KB Output is correct
20 Runtime error 274 ms 582048 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 282468 KB Output is correct
2 Correct 56 ms 282452 KB Output is correct
3 Correct 58 ms 282712 KB Output is correct
4 Correct 54 ms 282704 KB Output is correct
5 Correct 54 ms 282728 KB Output is correct
6 Correct 54 ms 282700 KB Output is correct
7 Correct 54 ms 282732 KB Output is correct
8 Correct 57 ms 282552 KB Output is correct
9 Correct 55 ms 282448 KB Output is correct
10 Correct 54 ms 282540 KB Output is correct
11 Correct 53 ms 282444 KB Output is correct
12 Correct 54 ms 282444 KB Output is correct
13 Correct 55 ms 282640 KB Output is correct
14 Correct 54 ms 282448 KB Output is correct
15 Correct 54 ms 282448 KB Output is correct
16 Correct 54 ms 282704 KB Output is correct
17 Correct 55 ms 282644 KB Output is correct
18 Correct 56 ms 282732 KB Output is correct
19 Correct 76 ms 288592 KB Output is correct
20 Runtime error 274 ms 582048 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -