最后十分钟没调出来,明明样例全过了,肉眼调错也没找出来
用的是按秩合并并查集
// 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;
}