社区讨论
新人求救,买铅笔那题,本机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 条回复,欢迎继续交流。
正在加载回复...