求助,本地测AC交上去全RE
查看原帖
求助,本地测AC交上去全RE
536745
WaTleZero_pt楼主2025/1/14 19:05

测试点 11 下载下来了能过但是交上去全都RE掉,显示“Aborted / IOT trap”

#include<bits/stdc++.h>
using namespace std;
template <class T>
struct Stack{
	vector<T> s;
	void push(T x){s.push_back(x);}
	T top(){return *(s.end()-1);}
	T second(){return *(s.end()-2);}
	T pop(){s.pop_back();}
	bool empty(){return s.empty();}
	int size(){return s.size();}
//	T val(int x){return s[x];}
};
const int N=100005;
vector<int> e[N],id[N];
int dfn[N],dep[N],f[N][20],cnt; 
void init(int u,int fa){
	dfn[u]=++cnt; dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<20;i++)
		f[u][i]=f[f[u][i-1]][i-1];
//	printf("%d %d %d\n",u,f[u][0],f[u][1]);
	for(int v:e[u]){
		if(v==fa) continue;
		init(v,u);
	}
}
int lca(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=19;i>=0;i--)
		if((dep[a]-dep[b])&(1<<i))
			a=f[a][i];
	if(a==b) return a;
	for(int i=19;i>=0;i--)
		if(f[a][i]!=f[b][i])
			a=f[a][i],b=f[b][i];
	return f[a][0];
}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
int n,m,k,u,v,r,a[N];
int val[N];
void virtualtree(){
//	printf("HERE\n");
	sort(a+1,a+r+1,cmp);
	Stack<int> st;
	st.push(0);
	st.push(0);
	st.push(a[1]);
	for(int i=2;i<=r;i++){
//		printf("HERE\n");
		int x=lca(st.top(),a[i]);
//		printf("%d %d %d\n",st.top(),a[i],x);
		if(x==st.top()){
			st.push(a[i]);
			continue;
		}
		while(dep[st.second()]>dep[x]){
			val[st.top()]++;
			val[st.second()]--;
//			printf("%d++ %d--\n",st.top(),st.second());
			st.pop();
		}
		val[st.top()]++;
		val[x]--;
//		printf("%d++ %d--\n",st.top(),x);
		st.pop();
		if(st.top()!=x)
			st.push(x);
		st.push(a[i]);
	}
	while(st.size()>3){
		val[st.top()]++;
		val[st.second()]--;
//		printf("%d++ %d--\n",st.top(),st.second());
		st.pop();
	}
}
int anslis[N],len;
void dfs(int u,int fa){
	vector<int>::iterator it=id[u].begin();
	for(int v:e[u]){
		if(v==fa){
			it++;
			continue;
		}
		dfs(v,u);
		val[u]+=val[v];
		if(val[v]>=k) anslis[++len]=*it;
//		printf("edge %d->%d (%d): %d\n",u,v,*it,val[v]);
		it++;
	}
}
int main(){
//	freopen("P6572_1.in","r",stdin);
//	freopen("myoutput.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		id[u].push_back(i);
		e[v].push_back(u);
		id[v].push_back(i);
	}
	init(1,0);
	for(int i=1;i<=m;i++){
		scanf("%d",&r);
		for(int j=1;j<=r;j++)
			scanf("%d",&a[j]);
		virtualtree();
	}
	dfs(1,0);
	printf("%d\n",len);
	sort(anslis+1,anslis+len+1);
	for(int i=1;i<=len;i++)
		printf("%d ",anslis[i]);
}
2025/1/14 19:05
加载中...