关于此代码开 O2 才能 AC 的问题
查看原帖
关于此代码开 O2 才能 AC 的问题
75765
Starlight237楼主2020/8/6 23:28

rt。如何解决?不开 O2 只有50分。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
extern "C" {
namespace io{
#define BUFS 100000
	static char in[BUFS], *p = in, *pp = in, out[BUFS << 7], *q = out, ch[20], *t = ch;
#define gc() (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
	inline ll read() {
		reg ll x = 0; reg char ch, f = 0;
		while (!isdigit(ch = gc())) f |= ch == '-';
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return f ? -x : x;
	}
	inline void write(ll x, char sp) {
		x || (*q++ = 48), x < 0 && (*q++ = '-', x = -x);
		while (x) *t++ = x % 10 + 48, x /= 10;
		while (t != ch) *q++ = *--t;
		*q++ = sp;
	}
	inline void flush() {fwrite(out, 1, q - out, stdout);}
}}
#define rd io :: read
#define wt io :: write
const int N = 250001;
struct Edge{int v, w, nxt;};
int e, ee[N];
struct Graph {
	int tot, head[N];
	Edge eg[N << 1];
	inline void addedge(int u, int v, int w) {
		eg[++tot] = Edge{v, w, head[u]}, head[u] = tot, ee[++e] = u;
	}
}g1, g2;
struct keypnt{int x, dfn;} kys[N];
inline bool cmp(const keypnt&a, const keypnt&b) {return a.dfn < b.dfn;}
int n, m, k, f[N][20], g[N][20], dep[N], dfn[N], tim, lg[N], ky[N];
ll dp[N];
void dfs(int x, int Fa, int w) {
	dfn[x] = ++tim, f[x][0] = Fa, dep[x] = dep[Fa] + 1, g[x][0] = w;
	for (reg int i = 1; i <= 18; ++i)
		f[x][i] = f[f[x][i - 1]][i - 1],
		g[x][i] = min(g[x][i - 1], g[f[x][i - 1]][i - 1]);
	for (reg int i = g1.head[x], v, w; i; i = g1.eg[i].nxt)
		(w = g1.eg[i].w, v = g1.eg[i].v) != Fa && (dfs(v, x, w), 0);
}
void DP(int x) {
	for (reg int i = g2.head[x], v, w; i; i = g2.eg[i].nxt)
		v = g2.eg[i].v, w = g2.eg[i].w, DP(v), ky[v] ? dp[x] += w : dp[x] += min(dp[v], (long long)w), ky[v] = 0, dp[v] = 0;
}
inline int LCA(int x, int y) {
	dep[x] < dep[y] && (swap(x, y), 0);
	while (dep[x] > dep[y]) x = f[x][lg[dep[x] - dep[y]]];
	if(x == y) return x;
	for (reg int i = lg[dep[x]]; i >= 0; --i)
		f[x][i] != f[y][i] && (x = f[x][i], y = f[y][i]);
	return f[x][0];
}
inline int DIS(int x, int y) {
	reg int ans = 0x3f3f3f3f;
	dep[x] < dep[y] && (swap(x, y), 0);
	while (dep[x] > dep[y])
		ans = min(ans, g[x][lg[dep[x] - dep[y]]]), x = f[x][lg[dep[x] - dep[y]]];
	return ans;
}
int S[N], *top = S;
inline void build() {
	g2.tot = 0;
	*++top = 1;
	for (reg int i = 1, u, lca, cur; i <= k; ++i) {
		u = kys[i].x, lca = LCA(u, *top);
		while (*top != lca)
			cur = *top, --top, dfn[*top] < dfn[lca] && (*++top = lca, 0),
			g2.addedge(*top, cur, DIS(*top, cur));
		*++top = u;
	}
	for (reg int u; *top != 1; g2.addedge(*top, u, DIS(*top, u))) u = *top, --top;
}
int main() {
	for (reg int i = 2; i <= N; ++i) lg[i] = lg[i >> 1] + 1;
	memset(g, 0x3f, sizeof g);
	n = rd();
	for (reg int i = 1, u, v, w; i < n; ++i)
		u = rd(), v = rd(), w = rd(), g1.addedge(u, v, w), g1.addedge(v, u, w);
	dfs(1, 0, 0);
	for (m = rd(); m; --m) {
		k = rd();
		for (reg int i = 1; i <= k; ++i)
			kys[i].x = rd(), ky[kys[i].x] = 1, kys[i].dfn = dfn[kys[i].x];
		sort(kys + 1, kys + k + 1, cmp);
		e = 0;
		build();
		DP(1);
		wt(dp[1], '\n'); dp[1] = 0;
		for (reg int i = 1; i <= e; ++i) g2.head[ee[i]] = 0;
		e = 0;
	}io :: flush();
	return 0;
}
2020/8/6 23:28
加载中...