EOJ Monthly 2021.10 Sponsored by TuSimple B. Secret(BFS）

 菜鸡只会做水题

// #pragma GCC optimize(2)
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <random>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define IO                       \ios::sync_with_stdio(false); \// cout.tie(0);
using namespace std;
// int dis[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, -1, 1, 1, -1, 1, -1, -1};
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);
// int dis[4][2] = {1, 0, 0, -1, 0, 1, -1, 0};
// int m[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct Edge
{int next, to;
} e[maxn];
int n, m, q, k, c;
int head[maxn];
int dis[maxn];
bool sec[maxn];
bool vis[maxn];
queue<int> qu;
int a[maxn];
int cnt = 0;void add(int u, int v)
{e[c].next = head[u];e[c].to = v;head[u] = c++;
}
void BFS()
{while (!qu.empty()){int u = qu.front();qu.pop();for (int i = head[u]; ~i; i = e[i].next){int v = e[i].to;if (vis[v] == true)continue;dis[v] = dis[u] + 1;vis[v] = true;qu.push(v);}}return;
}
int Get(int d)
{int L = 1, R = cnt;int ans;while (L <= R){int mid = (L + R) >> 1;if (a[mid] >= d){R = mid - 1;ans = mid;}elseL = mid + 1;}return ans;
}
int main()
{
#ifdef WXYfreopen("in.txt", "r", stdin);
//	 freopen("out.txt", "w", stdout);
#endifIO;int x, y;cin >> n >> m >> q >> k;memset(head, -1, sizeof head);int sum = 0;for (int i = 1;; i++){sum += i * k;if (sum >= n - 1)break;a[++cnt] = sum;}for (int i = 1; i <= q; i++){cin >> x;qu.push(x);sec[x] = true;vis[x] = true;dis[x] = 0;}for (int i = 0; i < m; i++){cin >> x >> y;add(x, y);add(y, x);}BFS();for (int i = 1; i <= n; i++){if (sec[i] == true){cout << 0 << " ";}else{int ans = Get(dis[i]);cout << ans << " ";}}return 0;
}