有什么警示的地方吗
查看原帖
有什么警示的地方吗
961149
xiao7_Mr_10_楼主2024/4/1 15:35

例如测试点19有些人的代码就出现了把9算成8的情况(比如说我),为什么会出现这种情况?

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct Point{
	int x,y;
	bool operator <(const Point &a)const{
		return x==a.x?y<a.y:x<a.x;
	}
};
struct edge{
	int x,y,val;
};
vector <edge> e[N<<1];
map <Point,int> mp;
struct ques{
	int op,x,y,val;
}wt[N];
int n,m,f[N],siz[N],s[N<<4],top,ans[N],op,tlhdl;
void insert(int x,int l,int r,int s,int t,Point k,int tag){
	if(l>=s&&r<=t){
		edge tmp=(edge){k.x,k.y,tag};
		e[x].push_back(tmp);
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)insert(x<<1,l,mid,s,t,k,tag);
	if(t>mid)insert(x<<1|1,mid+1,r,s,t,k,tag);
}
int getf(int u){
	if(f[u]==u)return u;
	return getf(f[u]);
}
void merge(int x,int y){
	x=getf(x),y=getf(y);
	if(siz[x]<siz[y])swap(x,y);
	s[++top]=y;
	if(x!=y)siz[x]+=siz[y];
	f[y]=x;
}
void del(){
	int x=s[top];
//	if(top==0)return;
	if(x!=f[x])siz[f[x]]-=siz[x];
	f[x]=x;
	top--;
}
int ans1[N];
void dfs(int x,int l,int r,int val){
	int last=top;
	for(int i = 0;i < e[x].size();i++)
		if(e[x][i].val<=val)
			merge(e[x][i].x,e[x][i].y);
	if(l==r){
		if(ans1[l]==-1&&getf(wt[l].x)==getf(wt[l].y)&&wt[l].op==2)
			ans1[l]=val;
	}
	else{
		int mid=(l+r)>>1;
		dfs(x<<1,l,mid,val);
		dfs(x<<1|1,mid+1,r,val);
	}
	while(last<top)del();
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> wt[i].op >> wt[i].x >> wt[i].y;
		if(wt[i].x>wt[i].y)swap(wt[i].x,wt[i].y);
		if(wt[i].op==0)cin >> wt[i].val;
	}
	memset(ans1,-1,sizeof(ans1));
	for(int i = 1;i <= m;i++){
		Point tmp=(Point){wt[i].x,wt[i].y};
		if(wt[i].op==0)mp[tmp]=i;
		else if(wt[i].op==1){
			insert(1,1,m,mp[tmp],i-1,tmp,wt[mp[tmp]].val);
			mp[tmp]=-1;
		}
	}
	for(int i = 1;i <= m;i++){
		Point tmp=(Point){wt[i].x,wt[i].y};
		if(mp[tmp]!=-1&&wt[i].op==0)insert(1,1,m,mp[tmp],m,tmp,wt[i].val);
	}
	for(int j = 0;j <= 10;j++){
		for(int i = 1;i <= n;i++)siz[i]=1,f[i]=i;
		dfs(1,1,m,j);
	}
	for(int i = 1;i <= m;i++)
		if(wt[i].op==2)
			cout << ans1[i] << "\n";
	return 0;
}
2024/4/1 15:35
加载中...