社区讨论

新人求救,买铅笔那题,本机AC,提交RE

P1909[NOIP 2016 普及组] 买铅笔参与者 21已保存回复 57

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
57 条
当前快照
1 份
快照标识符
@mi6y1o5g
此快照首次捕获于
2025/11/20 12:41
4 个月前
此快照最后确认于
2025/11/20 17:58
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define RI register int
using namespace std;

const int N = 600005;
const int M = 300005;
int n, m, sum, k, cnt1, xu[M], lg[M], depth[M], f[M][24], cost[N], head[N], nxt[N], to[N];
long long tot, lazy[M];

inline int read() {
	RI X = 0;register char c = 0;
	while(!isdigit(c = getchar()));
	while(isdigit(c)) X = (X << 1) + (X << 3) + (c ^ 48), c = getchar();
	return X;
}

inline void add(int u, int v, int w) { to[++cnt1] = v, cost[N] = w, nxt[cnt1] = head[u], head[u] = cnt1; }

inline void dfs1(int u, int fa) {
	for (RI i = head[u]; i; i = nxt[i])
		if (fa != to[i]) dfs1(to[i], u), lazy[u] += lazy[to[i]];
	if (u != 1 && lazy[u] == 1) ++tot;
	if (u != 1 && !lazy[u]) tot += m;
}

inline void dfs(int son, int father)
{
    depth[son] = depth[father] + 1, f[son][0] = father;
    for (RI i = 1; (1 << i) <= depth[son]; ++i)
        f[son][i] = f[f[son][i - 1]][i - 1];
    for (RI i = head[son]; i; i = nxt[i])
      	if (to[i] != father) dfs (to[i], son);
}

inline int LCA(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    while (depth[x] > depth[y]) x = f[x][lg[depth[x] - depth[y]] - 1];
    if (x == y) return x;
    for (RI i = lg[depth[x]]; i >= 0; --i)
    	if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline void ckm(int &x, long long y) { (x < y ? x = y : 0);}

int main() {
	freopen ("tree.in", "r", stdin);
	freopen ("tree.out", "w", stdout);
	n = read();
    for (RI i = 1; i <= n; ++i)
    	lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	for (RI i = 1, u, v; i <= 3; ++i)
		u = read(), v = read(), add(u, v, v), add(v, u, v), lazy[LCA(u,v)] -= 2, ++lazy[u], ++lazy[v], sum = ceil(n * 1.0 / u) * v, ckm(tot, sum);
	dfs(1, 0);
	dfs1(1, 0);
	cout << tot;
	return 0;
}

新人求教怎么办?????

回复

57 条回复,欢迎继续交流。

正在加载回复...