数据较弱?
  • 板块P11069 劫掠
  • 楼主qW__Wp
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/16 21:44
  • 上次更新2024/9/16 22:01:59
查看原帖
数据较弱?
453555
qW__Wp楼主2024/9/16 21:44

错误代码:

#include <bits/stdc++.h>
//#define int long long
#define INF 0x3fffffff
#define INFF 1e18
#define endl '\n'
#define lson id << 1
#define rson id << 1 | 1
#define LL long long
#define ULL unsigned long long

using namespace std;

const int N = 1e5 + 5;

int hd[N], cnt, d[N], dep[N], fa[N][30];

struct Edge {
	int to, nx;
} e[N << 1];

void add(int u, int v) {
	e[ ++ cnt] = {v, hd[u]}, hd[u] = cnt;
}

void dfs(int u, int fat, int D) {
	d[u] = dep[u] = D;
	fa[u][0] = fat;
	for (int i = hd[u]; i; i = e[i].nx) {
		int v = e[i].to;
		if (v == fat) continue;
		dep[v] = dep[u] + 1;
		dfs(v, u, D + 1);
		d[u] = max(d[u], d[v]);
	}
}

signed main() {
	int n, x, k; cin >> n >> x >> k;
	for (int i = 1; i < n; i ++) {
		int u, v; cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(x, 0, 0);
	for (int i = 1; i <= 29; i ++) {
		for (int j = 1; j <= n; j ++) {
			fa[j][i] = fa[fa[j][i - 1]][i - 1]; // 经典转移
		}
	}
	int ans = 0;
	for (int i = 1; i <= k; i ++) {
		int p; cin >> p;
		if (p == x) continue; // 特判!!!着火点和传送点在一起时不能计算贡献
		int l = dep[p] / 2; // 最多能向上走 l 步
		for (int j = 29; j >= 0; j --) {
			if (l >= (1 << j)) { // 向上倍增
				p = fa[p][j];
				l -= (1 << j);
			}
		}
		ans = max(ans, d[p]);
	}
	cout << ans;
	return 0;
}

5353

int l = dep[p] / 2;

应该是

int l = (dep[p] - 1) / 2;

但是两个都 AC 了

错误代码记录

正确代码记录

hack数据:

input:

15 1 1
10 2
2 1
10 11
11 12
12 13
13 14
14 15
10 6
6 7
7 8
8 9
6 5
5 4
5 3
5

正确代码output:

6

错误代码output:

7

如果是我造数据出了问题,很抱歉我浪费了你的时间,请打死我,否则请加强数据,谢谢。

2024/9/16 21:44
加载中...