QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#79770#5514. Mazenamelessgugugu16 105ms48840kbC++144.4kb2023-02-20 21:22:542023-02-20 21:22:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-20 21:22:58]
  • 评测
  • 测评结果:16
  • 用时:105ms
  • 内存:48840kb
  • [2023-02-20 21:22:54]
  • 提交

answer

#include <algorithm>
#include <cstdio>
#include <cstring>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
typedef unsigned long long ull;
const int N = 6000005;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int r, c, n;
char s[N];
int col[N];
inline bool inmap(int x, int y)
{
    return x >= 0 && x < r && y >= 0 && y < c;
}
inline int getid(int x, int y)
{
    return x * c + y;
}
inline void getpos(int id, int &x, int &y)
{
    x = id / c, y = id % c;
    return;
}
inline bool reach(int x1, int y1, int x2, int y2)
{
    int v1 = std::abs(x1 - x2), v2 = std::abs(y1 - y2);
    return v1 <= n && v2 <= n && (v1 < n || v2 < n);
}
inline bool reachid(int id1, int id2)
{
    int x1, y1, x2, y2;
    getpos(id1, x1, y1), getpos(id2, x2, y2);
    return reach(x1, y1, x2, y2);
}
int st, ed;
struct DSU
{
    int fa[N];
    inline void init(int l)
    {
        for (int i = 0; i < l; ++i)
            fa[i] = i;
        return;
    }
    int find(int x)
    {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline void merge(int x, int y)
    {
        fa[find(x)] = find(y);
        return;
    }
} Dr, Dc;
inline void del(int id)
{
    int x, y;
    getpos(id, x, y);
    Dr.merge(id, y == c ? r * c : id + 1);
    Dc.merge(id, x == r ? r * c : id + c);
    return;
}
int dis[N];
int stk[N], top;
int tmp[N], ttop;
int main(void)
{
    scanf("%d%d%d", &r, &c, &n);
    {
        int x, y;
        scanf("%d%d", &x, &y);
        st = getid(x - 1, y - 1);
        scanf("%d%d", &x, &y);
        ed = getid(x - 1, y - 1);
    }
    for (int i = 0; i < r;++i)
    {
        scanf("%s", s);
        for (int j = 0; j < c;++j)
            col[getid(i, j)] = s[j] == '#';
    }
    Dr.init(r * c + 1), Dc.init(r * c + 1);
    memset(dis, 0x3f, sizeof(dis)), dis[st] = 0, del(st);
    stk[++top] = st;
    while(1)
    {
        for (int i = 1;i <= top;++i)
        {
            int id = stk[i], x, y;
            if(id == ed)
                return printf("%d\n", dis[id]), 0;
            getpos(id, x, y);
            del(id);
            for (int o = 0; o < 4; ++o)
            {
                int nx = x + dx[o], ny = y + dy[o];
                if(!inmap(nx, ny))
                    continue;
                int yid = getid(nx, ny);
                if(!col[yid] && dis[yid] > dis[id])
                    dis[yid] = dis[id], stk[++top] = yid;
            }
        }
        memcpy(tmp, stk, sizeof(int) * (top + 5)), ttop = top, top = 0;
        for (int i = 1; i <= ttop;++i)
        {
            int id = tmp[i], x, y;
            if(reachid(id, ed))
                return printf("%d\n", dis[id] + 1), 0;
            getpos(id, x, y);
            int rl = std::max(0, x - n), rr = std::min(r - 1, x + n);
            int cl = std::max(0, y - n), cr = std::min(c - 1, y + n);
            int sp = 0, ep = 0;
            sp = getid(rl, cl + (!reach(rl, cl, x, y))), ep = getid(rl, cr - (!reach(rl, cr, x, y)));
            for (int u = Dr.find(sp); u <= ep;u = Dr.find(u))
            // for (int u = sp; u <= ep;++u)
                if(dis[u] > dis[id] + 1)
                    dis[stk[++top] = u] = dis[id] + 1, del(u);
            // , printf("a %d %d\n", id, u);
            sp = getid(rr, cl + (!reach(rr, cl, x, y))), ep = getid(rr, cr - (!reach(rr, cr, x, y)));
            for (int u = Dr.find(sp); u <= ep; u = Dr.find(u))
            // for (int u = sp; u <= ep; ++u)
                if (dis[u] > dis[id] + 1)
                    dis[stk[++top] = u] = dis[id] + 1, del(u);
            // , printf("b %d %d\n", id, u);
            sp = getid(rl + (!reach(rl, cl, x, y)), cl), ep = getid(rr - (!reach(rr, cl, x, y)), cl);
            for (int u = Dc.find(sp); u <= ep; u = Dc.find(u))
            // for (int u = sp; u <= ep; u += c)
                if (dis[u] > dis[id] + 1)
                    dis[stk[++top] = u] = dis[id] + 1, del(u);
            // , printf("c %d %d\n", id, u);
            sp = getid(rl + (!reach(rl, cr, x, y)), cr), ep = getid(rr - (!reach(rr, cr, x, y)), cr);
            for (int u = Dc.find(sp); u <= ep; u = Dc.find(u))
            // for (int u = sp; u <= ep; u += c)
                if (dis[u] > dis[id] + 1)
                    dis[stk[++top] = u] = dis[id] + 1, del(u);
            // , printf("d %d %d\n", id, u);
        }
    }
    puts("-1");
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 29152kb

input:

31 32 1
25 22
5 3
################################
################################
.###############################
.###############################
##..###############.############
###.###############.############
#####.##########################
###.#.##########################
###.##############...

output:

7

result:

wrong answer 1st lines differ - expected: '26', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #52:

score: 19
Accepted
time: 10ms
memory: 31104kb

input:

3 6 2
2 1
3 3
...###
..##..
#..###

output:

0

result:

ok single line: '0'

Test #53:

score: 0
Accepted
time: 0ms
memory: 29140kb

input:

4 24 4
3 4
3 3
..#...##.#...###...###.#
.##.#..##.##.##..#.####.
#.......#.#.#...#.#####.
######....######.#...#.#

output:

0

result:

ok single line: '0'

Test #54:

score: -19
Wrong Answer
time: 4ms
memory: 31180kb

input:

2 136 2
1 133
2 45
#############################################.##################.#.#######.##############.#################.##############.##.######.###
####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################

output:

21

result:

wrong answer 1st lines differ - expected: '41', found: '21'

Subtask #3:

score: 16
Accepted

Test #64:

score: 16
Accepted
time: 1ms
memory: 29132kb

input:

35 60 20
3 60
2 44
.#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####.
#.#......#.####..####...#...#......#........####....##.#.###
.#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##.
.#.#...##..#.##.......#......##......####...##.##..##.#....#
#...#.......#..#..#...#.#####.##.###....

output:

1

result:

ok single line: '1'

Test #65:

score: 0
Accepted
time: 8ms
memory: 27264kb

input:

63 602 3
10 463
3 402
#.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....

output:

9

result:

ok single line: '9'

Test #66:

score: 0
Accepted
time: 2ms
memory: 31508kb

input:

45 1194 5
4 632
37 206
...#..#............#..........#..##....##......#...##..#..#.............#...#...........##....#.........#.#.##..........#......#..........#.....#...........#........#.#.................#................#..........##.......................#.....#..........#........#........#......

output:

0

result:

ok single line: '0'

Test #67:

score: 0
Accepted
time: 4ms
memory: 29748kb

input:

244 245 244
28 168
222 200
...#...................................................................................................................................................................#..............................................................#..............
..............................

output:

0

result:

ok single line: '0'

Test #68:

score: 0
Accepted
time: 0ms
memory: 31488kb

input:

244 245 244
175 140
70 11
##.##....###.###..######..###.#.#####.##..#.#####.#.###.###.....#....###.#####.##..#.###.####.#..##.####...#.#####.###.##..#######.##.##...#..####.#...#####.##.###.#....##..####.###.#.#####..#.#.##.###.#..#.##.####..#.#.#...#######.######.##.#..
#..#..##.####.###.###..........

output:

1

result:

ok single line: '1'

Test #69:

score: 0
Accepted
time: 3ms
memory: 31404kb

input:

244 245 244
241 52
100 202
#######.###################################################################################################################################################################.#########################################################################
###########################...

output:

1

result:

ok single line: '1'

Test #70:

score: 0
Accepted
time: 2ms
memory: 29652kb

input:

62 967 62
41 1
29 386
####.######.####.#####...##.##..##.####..######.##...######....#.#..#...#.#.###.##.###...######..#.#.####.###.##.###.#...###..##..####.####.#.#...###..#.#..#..###.....#####.##..##.####..##......#.####.##.#...##..###.#....#..##.###.#..#####.#..#.#.#.##..#..#.#..##.##.####...#.#....

output:

6

result:

ok single line: '6'

Test #71:

score: 0
Accepted
time: 14ms
memory: 32032kb

input:

202 595 58
71 324
182 516
..#.###....#.##......#............#...#.###....................#....#....#...#.##.........#.....#....#.#.......###.#........#####..#.......###......#......#.......#...##..........#.#.....#.#.................#.#...#..#.#.......#.#.##...#.#..#......#.....#.......#.#..#..#.......

output:

0

result:

ok single line: '0'

Test #72:

score: 0
Accepted
time: 8ms
memory: 32712kb

input:

387 387 387
100 184
358 250
................#...........................................................................................................................................#......................................................................................................................

output:

0

result:

ok single line: '0'

Test #73:

score: 0
Accepted
time: 9ms
memory: 32012kb

input:

387 387 387
133 20
329 125
#..##.##..###.##.##..######..#####.#.#####..#####.####.#....##.#.#.#.#.##.##..##.###....#.#..#.#.##...###########..##..#.##..##.######.##.#.#####.###.##.#....#..##.##.##.#####..#.##.##.####..#.###.##.##.#.#....###...#.#.###.##..####..##.##.#.#.#.#.###....#.###.#.#..#.###.#...

output:

1

result:

ok single line: '1'

Test #74:

score: 0
Accepted
time: 3ms
memory: 32356kb

input:

387 387 387
201 41
238 340
###########################################################################.#####################################################################################################################################################################################################...

output:

1

result:

ok single line: '1'

Test #75:

score: 0
Accepted
time: 15ms
memory: 35328kb

input:

601 723 26
258 272
578 200
#.#.....#..#.##.##.##.......#.......#...#..#.....##...##.##..###.....#.....#.#.#....###...#.#....#...##..#..#.####...#..#..#.......#..##.....###...#.#.#....#....####..###.#.##..##....##.....##.#..#.##.#.#....#......#...##.....##.......#..#.#...#..#..##...#...#....####.##.#...

output:

0

result:

ok single line: '0'

Test #76:

score: 0
Accepted
time: 57ms
memory: 46060kb

input:

103 12319 67
96 7020
42 1423
..##.###......#...#...#.........#........#....#..#...##.......#..###......###...#...##..#.##.##......##..#....#..............#.#......#.#...#...#..#..##.#..#....#.........###...#.....#..#..###...#.......#..#...##...#..####.##.#.##..##...#..#..####...#.......#.#....#..#.#...

output:

0

result:

ok single line: '0'

Test #77:

score: 0
Accepted
time: 105ms
memory: 47908kb

input:

1224 1225 1224
582 110
326 1104
..................................................................................#...........................................................................................................................................................#................................

output:

0

result:

ok single line: '0'

Test #78:

score: 0
Accepted
time: 19ms
memory: 44860kb

input:

1224 1225 1224
1024 851
437 463
##..#.###.####..##..#...#.#...##.#.#.########.#.#####..##..##.###..##..##..##.#...#.##.##.#####..###########.#.##...#.###########.####..####...#......##...###..#.#.####.#####.#.####.####.##..#.######..#.#.##.#.#.#.####....#...###.##...#..#..#####..#.#####.#...##.##......

output:

1

result:

ok single line: '1'

Test #79:

score: 0
Accepted
time: 12ms
memory: 42512kb

input:

1224 1225 1224
188 85
758 1157
#####.##.########################################################################################################################################################.###############################################################.###########################################...

output:

1

result:

ok single line: '1'

Test #80:

score: 0
Accepted
time: 54ms
memory: 47744kb

input:

72 20833 72
41 567
6 17116
##.....##.##..#..###....###.#..##..#.#...#......#.#..###.#..#.#.#..##..#.##.......#...#.###..##.#.#..#....#....##..........#..#...##...#........#..#.#.##.###.#.###....###.#....#.#...#....#.##..#.#.##.#######.#...##....#.#.......##..#..#...##.##.........#..#....#..###.##......

output:

0

result:

ok single line: '0'

Test #81:

score: 0
Accepted
time: 46ms
memory: 48840kb

input:

114 13157 114
100 43
54 9728
.....#.....##.##....##.#..###.###.#..#.#...#....#.##.....#..#.#.###................###...#..#..#.##.#...#..#.##........#...#.#..##...#..###..##.#.....#.#.....#.....##.....#.##..#.#....#..#.##..#..##..#.###.##...#.#.#.#..##...#...#...#.##.##.#.#....#..#.#.........#....##....

output:

0

result:

ok single line: '0'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%