Luogu P2024 [NOI2001]食物链

ゝ一世哀愁。 2023-06-02 13:59 11阅读 0赞

#include<cstdio>
    #include<cstring>
    using namespace std;
    
    int n,k,fa[1000005],ans;
    
    inline int getfa(int v){
        return fa[v]==v?v:fa[v]=getfa(fa[v]);
    }
    
    inline void merge(int x,int y){
        x=getfa(x);y=getfa(y);
        if(x!=y)fa[y]=x;
    }
    
    inline bool family(int x,int y){
        return getfa(x)==getfa(y);
    }
    
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=3*n;i++)fa[i]=i;
        for(int i=1;i<=k;i++){
            int opt,x,y;
            scanf("%d%d%d",&opt,&x,&y);
            if(x>n||y>n){ans++;continue;}
            if(opt==1){
                if(family(x,y+n)||family(x,y+2*n)){ans++;continue;}
                merge(x,y);
                merge(x+n,y+n);
                merge(x+2*n,y+2*n);
            }
            else{
                if(x==y){ans++;continue;}
                if(family(x+2*n,y)||family(x,y)){ans++;continue;}
                merge(x+n,y);
                merge(x,y+2*n);
                merge(x+2*n,y+n);//是个环：猎物的猎物是天敌 
            }
        }
        printf("%d\n",ans);
    }
    //x+n:猎物 x+2*n:天敌

转载于:https://www.cnblogs.com/Y15BeTa/p/11428044.html

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 Luogu P2024 [NOI2001]食物链

include<cstdio> include<cstring> using namespace std; int n,k,fa[10

ゝ一世哀愁。/ 2023年06月02日 13:59/ 0 赞/ 12 阅读

相关 LuoGu P1368 工艺

[LuoGu P1368 工艺][LuoGu P1368] 最小表示法的板子题.这个题可以用\\(n\\:log\_2\\:n\\)的\\(SA\\)求最小表示法也可以用更

雨点打透心脏的1/2处/ 2023年06月02日 11:59/ 0 赞/ 19 阅读

相关 P2024- [NOI2001]食物链

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

傷城~/ 2023年06月01日 08:47/ 0 赞/ 16 阅读

相关 P2024 [NOI2001]食物链

P2024 \[NOI2001\]食物链 ![博客图片][format_png] 题目链接 [P2024 \[NOI2001\]食物链][P2024 _NOI20

男娘i/ 2023年03月04日 14:28/ 0 赞/ 31 阅读

相关【滚动数组】【状压DP】NOI2001炮兵阵地

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 题目描述司令部的将军们打算在NM的网格地

比眉伴天荒/ 2022年01月09日 05:41/ 0 赞/ 248 阅读

相关 P2024 食物链

题面:[https://www.luogu.org/problemnew/show/P2024][https_www.luogu.org_problemnew_show_P20

傷城~/ 2021年11月22日 08:54/ 0 赞/ 242 阅读

相关 Luogu2375 [NOI2014]动物园（KMP）

写炸，上网，不同KMP形态。无力，照该，一换写法就过。横批：我是垃圾求\\(next\\)时\\(DP\\)出\\(num\\)，路径压缩防卡\\(n^2

系统管理员/ 2021年11月17日 05:12/ 0 赞/ 337 阅读

相关【题解】Luogu P5468 [NOI2019]回家路线

[原题传送门][Link 1] 前置芝士：斜率优化不会的可以去[杜神博客][Link 2]学这道题我考场上只会拆点跑最短路的70pts做法后来回家后发

水深无声/ 2021年10月30日 03:22/ 0 赞/ 348 阅读

相关【题解】Luogu P5471 [NOI2019]弹跳

[原题传送门][Link 1] 先考虑部分分做法： subtask1：暴力\\(O(nm)\\)枚举，跑最短路 subtask2: 吧一行的点压到vecto

逃离我推掉我的手/ 2021年10月20日 00:20/ 0 赞/ 330 阅读

相关 bzoj1491 luogu2047 [NOI2007]社交网络

[https://www.lydsy.com/JudgeOnline/problem.php?id=1491][https_www.lydsy.com_JudgeOnline_

叁歲伎倆/ 2021年10月18日 16:20/ 0 赞/ 300 阅读