Link

现在MLE80->TIE80，手写内存池为单向链表动态分配空间试图省空间，结果T飞？

TLE80代码（不厌氧，不喜氧）：

#include <cstdio>
#include <cstring>
#include <vector>

const int N = 200005, M = 400005;
namespace Memory_Pool {
	int memtot;
	struct node {
		int x, next;
	} memory[500005];
	std::vector<int> freehead;
	struct Vector {
		int head, tail;
		struct node {
			int x, next;
		};
		inline void push_back(const int x) {
			int flag(0);
			if (freehead.size()) {
				int t(*(freehead.end() - 1));
				flag = t, t = memory[t].next;
				freehead.pop_back();
				if (t != 0) freehead.push_back(t);
			}
			else flag = ++ memtot;
			memory[tail].next = flag;
			memory[tail = flag].x = x, memory[flag].next = 0;
		}
		inline void clear() {freehead.push_back(head); head = 0;}
	};
}

Memory_Pool::Vector sons[N];
int fa[N], ans[N], l[N], r[N], tim, n, m;
struct Edge {
	int u, v;
} e[M];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void join(const int x, const int y) {
	int fx(find(x)), fy(find(y));
	if (fx == fy) return;
	if (fy == 1) fx ^= fy ^= fx ^= fy;
	if (sons[fy].head)
	for (int i(sons[fy].head); i; i = Memory_Pool::memory[i].next) {
		int t(Memory_Pool::memory[i].x);
		sons[fx].push_back(t);
		if (fx == 1) ans[t] = tim - 1;
		fa[t] = fx;
	}
	sons[fy].clear();
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i(1); i <= n; ++ i)
		scanf("%d%d", l + i, r + i), fa[i] = i, sons[i].head = sons[i].tail = i,
		Memory_Pool::memory[i].x = i;
	Memory_Pool::memtot = n;
	for (int i(1); i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (y == 1 && l[x] != -1) e[i] = Edge{x, l[x]}, l[x] = -1;
		else if (y == 2 && r[x] != -1) e[i] = Edge{x, r[x]}, r[x] = -1;
	}
	
	for (int i(1); i <= n; ++ i) {
		if (l[i] != -1) join(i, l[i]);
		if (r[i] != -1) join(i, r[i]);
	}
	memset(ans, -1, sizeof ans);
	for (tim = m; tim; -- tim) join(e[tim].u, e[tim].v);
	for (int i(1); i <= n; ++ i) printf("%d\n", ans[i]);
	return 0;
}