[ABC254E] Small d and k Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个点 $m$$m$ 条边的简单无向图，特别地，保证每个点的度数不超过 $3$$3$。$q$$q$ 次询问，给定 $x,k$$x, k$，求所有距离 $x$$x$ 不超过 $k$$k$ 的点（包括 $x$$x$）的编号和。

Solution

属实是一道水题，最开始还在想有什么性质，比如是不是最多是一棵二叉树之类的。。。然后突然发现保证了 $0\le k_i\le 3$$0 \le k_i \le 3$，于是这道题就变成了一道无脑宽搜了。图建出来之后每次询问在 $x$$x$ 点宽搜一下即可。只需要注意判一下 vis 和注意别漏了 $x$$x$ 本身即可，最终复杂度即为 $O(3^{k}q)$$O(3^kq)$，显然能过。

Code

xxxxxxxxxx
83
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
struct Edge{
26
    Edge* nxt;
27
    int to;
28
    OPNEW;
29
}ed[610000];
30
ROPNEW(ed);
31
Edge* head[160000];
32

33
int N, M;
34
bitset < 160000 > vis;
35

36
int bfs(int S, int D){
37
    if(!D)return S;
38
    basic_string < int > nods;
39
    queue < pair < int, int > > cur;
40
    cur.push({S, 0}), vis[S] = true, nods += S;
41
    while(!cur.empty()){
42
        auto tp = cur.front(); cur.pop();
43
        for(auto i = head[tp.first]; i; i = i->nxt)
44
            if(!vis[SON]){
45
                vis[SON] = true;
46
                nods += SON;
47
                if(tp.second + 1 < D)cur.push({SON, tp.second + 1});
48
            }
49
    }int ret(0);
50
    for(auto nod : nods)vis[nod] = false, ret += nod;
51
    return ret;
52
}
53

54
int main(){
55
    N = read(), M = read();
56
    for(int i = 1; i <= M; ++i){
57
        int s = read(), t = read();
58
        head[s] = new Edge{head[s], t};
59
        head[t] = new Edge{head[t], s};
60
    }int Q = read();
61
    while(Q--){
62
        int S = read(), D = read();
63
        printf("%d\n", bfs(S, D));
64
    }
65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69
template < typename T >
70
inline T read(void){
71
    T ret(0);
72
    int flag(1);
73
    char c = getchar();
74
    while(c != '-' && !isdigit(c))c = getchar();
75
    if(c == '-')flag = -1, c = getchar();
76
    while(isdigit(c)){
77
        ret *= 10;
78
        ret += int(c - '0');
79
        c = getchar();
80
    }
81
    ret *= flag;
82
    return ret;
83
}

UPD

update-2022_12_06 初稿