关于 devcpp
  • 板块灌水区
  • 楼主haochengw920
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/4/14 21:06
  • 上次更新2024/4/15 08:58:45
查看原帖
关于 devcpp
563650
haochengw920楼主2024/4/14 21:06

我在这份代码中 :

#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#define int long long
#define INF (0x3f3f3f3f)
using namespace std;

char buf[3000000], *p1 = buf, *p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,3000000,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	int x = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}

const int MAXN = 1000005;

int n, Q;
struct edge {
	int to, nex, dis;
}e[MAXN]; int idx, head[MAXN];
inline void add(int u, int v, int w) {
	e[++ idx].to = v;
	e[idx].dis = w;
	e[idx].nex = head[u];
	head[u] = idx;
}

namespace Prew {
	int timer, dep[MAXN];
	int dfn[MAXN], eu[MAXN];
	int lg[MAXN], f[MAXN][25];
	inline void dfs(int u, int fath) {
		eu[dfn[u] = ++ timer] = u;
		for (int i = head[u]; i; i = e[i].nex) {
			int v = e[i].to;
			if (v == fath) continue;
			dep[v] = dep[u] + e[i].dis;
			dfs(v, u), eu[++ timer] = u;
		}
	} 
	inline int _min(const int &x, const int &y) {
		return dep[x] < dep[y] ? x : y;
	}
	inline void Init() {
		for (int i = 1; i <= timer; ++ i)
			f[i][0] = eu[i];
		for (int i = 2; i <= timer; ++ i)
			lg[i] = lg[i >> 1] + 1;
		for (int j = 1; j <= lg[timer]; ++ j)
			for (int i = 1; i <= timer; ++ i) {
				f[i][j] = f[i][j - 1];
				if (i + (1 << (j - 1)) <= timer)
					f[i][j] = _min(f[i][j], f[i + (1 << (j - 1))][j - 1]);
			}
	}
	inline int Getlca(int u, int v) {
		int l = min(dfn[u], dfn[v]);
		int r = max(dfn[u], dfn[v]);
		int len = lg[r - l + 1];
		return _min(f[l][len], f[r - (1 << len) + 1][len]);
	}
	inline int dist(int u, int v) {
		int lca = Getlca(u, v);
		return dep[u] + dep[v] - dep[lca] - dep[lca];
	}
	inline void prewmain() {
		n = read();
		for (int i = 1; i < n; ++ i) {
			int u = read(), v = read(), w = read();
			add(u, v, w); add(v, u, w);
		}
		dfs(1, 0); Init();
	} 
}
struct Points { 
	int x, y;
}a[MAXN * 20]; int pn;
namespace Getpts {
	int nd[MAXN], tp;
	int siz[MAXN], fg[MAXN];
	inline void dfs1(int u, int fath) {
		nd[++ tp] = u, siz[u] = 1;
		for (int i = head[u]; i; i = e[i].nex) {
			int v = e[i].to;
			if (v == fath || fg[v]) continue;
			dfs1(v, u); siz[u] += siz[v];
		}
	}
	inline int Getrt(int x) {
		tp = 0; dfs1(x, 0);
		int nw = x, res = tp;
		for (int i = 1; i <= tp; ++ i)
			if (max(siz[nd[i]], tp - siz[nd[i]]) < res)
				nw = nd[i], res = max(siz[nd[i]], tp - siz[nd[i]]);
		return nw;
	}
	int dep[MAXN];
	inline void dfs2(int u, int fath) {
		for (int i = head[u]; i; i = e[i].nex) {
			int v = e[i].to;
			if (v == fath || fg[v]) continue;
			dep[v] = dep[u] + e[i].dis;
			dfs2(v, u);
		}
	}
	int stc[MAXN], top;
	inline void Solve(int rt) {
		dep[rt] = 0; dfs2(rt, 0);
		sort(nd + 1, nd + tp + 1);
		top = 0;
		for (int i = 1; i <= tp; ++ i) {
			while (top && dep[nd[i]] < dep[stc[top]])
				-- top;
			if (top) a[++ pn] = (Points){stc[top], nd[i]};
			stc[++ top] = nd[i];
		}
		top = 0;
		for (int i = tp; i; -- i) {
			while (top && dep[nd[i]] < dep[stc[top]])
				-- top;
			if (top) a[++ pn] = (Points){nd[i], stc[top]};
			stc[++ top] = nd[i];
		}
		fg[rt] = 1;
		for (int i = head[rt]; i; i = e[i].nex)
			if (!fg[e[i].to]) Solve(Getrt(e[i].to));
	}
	inline void getmain() {
		Solve(Getrt(1));
	}
}
class BIT {
	private : 
	int tr[MAXN];
	inline int lowbit(int x) {
		return (x & (-x));
	}
	public : 
	inline BIT() {
		memset(tr, 0x3f, sizeof(tr));
	}
	inline void Modify(int p, int x) {
		for (; p; p -= lowbit(p))
			tr[p] = min(tr[p], x); 
	}
	inline int Query(int p) {
		int res = INF;
		for (; p <= n; p += lowbit(p))
			res = min(res, tr[p]);
		return res;
	}
};
struct Qry {
	int l, r, id;
	inline bool operator < (const Qry &y) const {
		return r < y.r;
	}
}q[MAXN];
namespace Ansq {
	BIT st;
	int ans[MAXN];
	vector<Points>vec[MAXN];
	inline void Solve() {
		Q = read();
		for (int i = 1; i <= Q; ++ i)
			q[i].l = read(), q[i].r = read(), q[i].id = i;
		sort(q + 1, q + Q + 1);
		for (int i = 1; i <= pn; ++ i)
			vec[a[i].y].push_back(a[i]);
		int pt = 1;
		for (int i = 1; i <= Q; ++ i) {
			for (; pt <= q[i].r; ++ pt)
				for (Points u : vec[pt])
					st.Modify(u.x, Prew::dist(u.x, u.y)); 
			ans[q[i].id] = st.Query(q[i].l); 
		}
		for (int i = 1; i <= Q; ++ i)
			printf ("%lld\n", ans[i] == INF ? -1 : ans[i]);
	}
}

signed main()
{
	Prew::prewmain();
	Getpts::getmain();
	Ansq::Solve();
	return 0;
}

错误地定义了 long long 的 INF 为 0x3f3f3f3f ,但是在 devcpp 却能输出正确的结果,甚至我在极限数据下对拍了 3 分钟都没有出错。

我已经开启了 -Wall 指令,却没有什么用处,请问什么办法可以避免这种错误?

2024/4/14 21:06
加载中...