社区讨论

20pts求助,一寒假没写题不会做了

P2024[NOI2001] 食物链参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mmagvxh9
此快照首次捕获于
2026/03/03 18:30
上周
此快照最后确认于
2026/03/04 09:24
7 天前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4;
int n,k,x,y,ans;
int f[N],eat[N],ate[N];
//f为并查集,eat[a]=b表示a吃b,ate[a]=b表示b被a吃
char c;
inline void init(){
    for(int i=1;i<=n;i++)
        f[i]=eat[i]=ate[i]=i;
}inline int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}inline void merge(int x,int y){
    f[find(x)]=find(y);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>k;init();
    for(int i=1;i<=k;i++){
        cin>>c>>x>>y;
        if(x>n||y>n){
            ans++;
            continue;
        }else{
            if(c=='1'){
                if(x==y) continue;
                if(eat[f[x]]==f[y]||eat[f[y]]==f[x]){
                    ans++;
                    continue;
                }merge(x,y);
            }else{
                if(f[x]==f[y]){
                    ans++;
                    continue;
                }if(eat[x]==x) eat[x]=y;
                else merge(eat[x],y);
                if(ate[y]==y) ate[y]=x;
                else merge(x,ate[y]);
            }
        }
    }cout<<ans;
    return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...