Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#452#79. 「NOIP2017」奶酪Pigsyy100161ms5568kbC++231.7kb2025-04-24 13:51:032025-04-24 13:51:04

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#define max(A,B) (A>B?A:B)
#define min(A,B) (A<B?A:B)
#define ll long long
#define int long long
const int N = 2e5 + 5;
const int M = 505;
const int INF = 0x3f3f3f3f;
using namespace std;

inline int read() {
    int s = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }

    return  s * f;
}

int n, m, h, r, flag, vis[N];

struct node {
    int x, y, z;
} a[N];

inline bool ask(node q, node p) {
    int d = (q.x - p.x) * (q.x - p.x) + (q.y - p.y) * (q.y - p.y) + (q.z - p.z) * (q.z - p.z);

    if (d <= 4 * r * r)
        return true;

    return false;
}

void dfs(int now) {
    if (flag)
        return ;

    if (a[now].z + r >= h) {
        flag = 1;
        return ;
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i])
            continue;

        if (!ask(a[i], a[now]))
            continue;

        vis[i] = 1;
        dfs(i);
    }
}

signed main() {
    //  freopen("cheese.in","r",stdin);
    //  freopen("cheese.out","w",stdout);
    int T = read();

    while (T--) {
        n = read(), h = read(), r = read() ;
        flag = 0;

        for (int i = 1; i <= n; i++)
            a[i].x = read(), a[i].y = read(), a[i].z = read(), vis[i] = 0;

        for (int i = 1; i <= n; i++)
            if (a[i].z <= r)
                vis[i] = 1, dfs(i);

        if (flag)
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 5524kb

input:

5
1 100 60
70 27 88
1 100 75
80 39 34
1 100 50
605 563 50
1 200 160
120 176 40
1 200 10
50 47 84

output:

No
Yes
Yes
Yes
No

result:

ok 5 tokens

Test #2:

score: 10
Accepted
time: 4ms
memory: 5328kb

input:

20
1 1000 563
79 29 664
1 1000 642
934 972 673
1 1000 500
356 256 76
1 1000 498
252 32 672
1 1000 99...

output:

No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes

result:

ok 20 tokens

Test #3:

score: 10
Accepted
time: 0ms
memory: 5188kb

input:

6
2 1000 250
0 0 250
0 0 751
2 1000 400
400 750 5
840 716 718
3 2000 600
328 1454 1005
114 736 1503
...

output:

No
No
No
No
No
Yes

result:

ok 6 tokens

Test #4:

score: 10
Accepted
time: 2ms
memory: 5208kb

input:

20
8 8535 7995
-2894 -344 102
-368 -8400 3331
6732 4330 3462
9929 9940 430
205 -2958 1596
-4440 432 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes

result:

ok 20 tokens

Test #5:

score: 10
Accepted
time: 4ms
memory: 5356kb

input:

5
1000 4928 258
-7744 9886 3739
2325 7894 4178
5520 6510 3780
-1886 -5269 142
1301 8784 2122
-6921 4...

output:

No
Yes
No
Yes
Yes

result:

ok 5 tokens

Test #6:

score: 10
Accepted
time: 20ms
memory: 5536kb

input:

10
1000 5108 828
-976 -7844 5051
7232 -8508 1564
-6275 6927 3465
-6018 7088 1644
2672 9265 1936
7818...

output:

Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes

result:

ok 10 tokens

Test #7:

score: 10
Accepted
time: 35ms
memory: 5496kb

input:

20
1000 5131 531
-8405 125 4237
9480 3440 2981
-8310 8496 4984
-9910 -5463 2701
-258 -5683 3899
2792...

output:

Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
No

result:

ok 20 tokens

Test #8:

score: 10
Accepted
time: 29ms
memory: 5548kb

input:

20
2 5202 1301
0 0 1301
102 0 3901
2 5202 1301
0 0 1301
102 1 3901
1000 7236 649
-7117 -6085 4914
74...

output:

Yes
No
Yes
Yes
Yes
No
Yes
No
No
No
Yes
No
No
No
Yes
Yes
Yes
No
Yes
No

result:

ok 20 tokens

Test #9:

score: 10
Accepted
time: 37ms
memory: 5568kb

input:

20
2 5100500 1275250
0 0 1275250
0 50500 3825250
1000 95100603 1624126
-83359625 75545594 84471552
-...

output:

Yes
No
No
No
Yes
No
Yes
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No

result:

ok 20 tokens

Test #10:

score: 10
Accepted
time: 30ms
memory: 5352kb

input:

20
2 5100500 1275250
0 0 1275250
1 50500 3825250
1000 94972653 9368205
-99057506 56850186 89511048
8...

output:

No
Yes
Yes
No
No
Yes
Yes
No
No
No
No
No
Yes
No
No
Yes
No
No
No
Yes

result:

ok 20 tokens