RT

提交 20 分 全 TLE

然鹅数据在本地可以跑（0.2s）

开了 O2 可以过 90

推测是数组越界之类的 ub……有没有 dalao 帮个忙 /kel

#include <bits/stdc++.h>
using namespace std;
struct Edge
{
	int to, nxt;
}re[2000020], e[2000020];
int recnt = 0, ecnt = 0, rhead[66000], head[66000];
inline void addedge(Edge *e, int *head, int &ecnt, int from, int to)
{
	e[ecnt].to = to;
	e[ecnt].nxt = head[from];
	head[from] = ecnt++;
}
int in[66000];
int dep[66000], fa[66000];
queue<int> topo;
int st[66000][23];
inline void upd(int u)
{
	st[u][0] = u;
	for(int i = 1; i <= 20; i++)
		st[u][i] = st[fa[st[u][i - 1]]][i - 1];
}
inline void up(int &u, int &v)
{
	if(dep[u] < dep[v])
		swap(u, v);
	int dt = dep[u] - dep[v];
	for(int i = 20; i >= 0; i--)
		if(dt >= (1 << i))
		{
			dt -= (i << i);
//			assert(st[u][i] != -1);
//			assert(u >= 0 && u <= 65536);
//       这两句 assert 加上就 TLE -> RE 因此推测是某个地方越界 QAQ
			u = fa[st[u][i]];
			if(!dt)
				break;
		}
}
inline int LCA(int u, int v)
{
	if(u == -1)
		return v;
	up(u, v);
	for(int i = 20; i >= 0; i--)
		if(st[u][i] != st[v][i])
		{
			u = fa[st[u][i]];
			v = fa[st[v][i]];
			if(u == v)
				break;
		}
	return u;
}
int newin[66000], sz[66000];
queue<int> q;
int main()
{
//	freopen("1.txt", "r", stdin);
//	freopen("2.txt", "w", stdout);
	memset(head, -1, sizeof(head));
	memset(rhead, -1, sizeof(rhead));
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		while(x)
		{
			addedge(e, head, ecnt, i, x);
			addedge(re, rhead, recnt, x, i);
			in[i]++;
			scanf("%d", &x);
		}
	}
	for(int i = 1; i <= n; i++)
		if(!in[i])
		{
			topo.push(i);
			addedge(e, head, ecnt, i, 0);
			addedge(re, rhead, recnt, 0, i);
		}
	fa[0] = 0;
	dep[0] = 0;
	upd(0);
	while(!topo.empty())
	{
		int u = topo.front();
		topo.pop();
		for(int i = rhead[u]; i != -1; i = re[i].nxt)
		{
			int v = re[i].to;
			in[v]--;
			if(in[v] == 0)
				topo.push(v);
		}
		int lca = -1;
		for(int i = head[u]; i != -1; i = e[i].nxt)
		{
			int v = e[i].to;
//			assert()
			lca = LCA(lca, v);
		}
		fa[u] = lca;
		dep[u] = dep[lca] + 1;
		newin[lca]++;
		upd(u);
	}
	for(int i = 1; i <= n; i++)
		if(newin[i] == 0)
			q.push(i);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		sz[u]++;
		sz[fa[u]] += sz[u];
		newin[fa[u]]--;
		if(newin[fa[u]] == 0)
			q.push(fa[u]);
	}
	for(int i = 1; i <= n; i++)
		printf("%d\n", sz[i] - 1);
	return 0;
}