求助刚刚的ABC F
  • 板块学术版
  • 楼主Rnfmabj
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/11/11 21:43
  • 上次更新2023/11/12 15:37:15
查看原帖
求助刚刚的ABC F
93707
Rnfmabj楼主2023/11/11 21:43

最后十分钟没调出来,明明样例全过了,肉眼调错也没找出来

用的是按秩合并并查集

// Problem: F - Good Set Query
// Contest: AtCoder - Toyota Programming Contest 2023#7(AtCoder Beginner Contest 328)
// URL: https://atcoder.jp/contests/abc328/tasks/abc328_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//空中散歩の SOS 僕ファー 僕ファー 僕ファー ~
#include<bits/stdc++.h>
#define ll long long
#define db double
#define R read()
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
using namespace std;
inline ll read() {
	ll s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f*=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
inline void write(ll x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10),x%=10;
	putchar('0'+x);
}//Don't use it for CF.
inline void wk(ll x){write(x);putchar(' ');}
inline void we(ll x){write(x);putchar('\n');}
const ll maxn=2e5+5;
// ll ls[maxn],rs[maxn],val[maxn];
ll fa[maxn],del[maxn],h[maxn];
ll get_fa(ll x){
	if(fa[x]!=x)return get_fa(fa[x]);
	return x;
}
ll get_val(ll x){//获得当前的值
	if(fa[x]!=x)return del[x]+get_val(fa[x]);
	return 0;
}
void merge(ll x,ll y,ll s){//按秩合并
	ll u=get_fa(x),v=get_fa(y);
	if(h[u]<h[v])swap(x,y),swap(u,v),s=-s;
	ll sum=get_val(x);
	del[v]=sum-s;
	fa[v]=u;
	h[u]=(h[u]==h[v]?h[u]+1:h[u]);
}
void solve(){
	ll n=R,m=R;
	for(ll i=1;i<=n;i++)fa[i]=i,h[i]=1;//初始化,默认每个数初始权值为0
	for(ll i=1;i<=m;i++){
		ll a=R,b=R,c=R;
		if(get_fa(a)==get_fa(b)){
			if(get_val(a)-get_val(b)!=c)continue;
			else wk(i);
		}
		else merge(a,b,c),wk(i);
	}
	return ;
}
ll T=1;
signed main(){
//	T=R;
	for(ll kase=1;kase<=T;kase++){
		solve();
	}
	return 0;
}
2023/11/11 21:43
加载中...