codeforces_C. Case of Matryoshkas

一时失言乱红尘 2022-08-01 14:56 20阅读 0赞

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    int pre[100010];  //pre[i]==x 表示 i 被 x 嵌套  嵌套自己表示单独的一个，没有被嵌套
    
    int main()
    {
    
        int n=in(),k=in();
    
        for(int i=0;i<=n;i++) pre[i]=i;
        while(k--)
        {
            int t=in();
            int now=in();
            --t;
            while(t--)
            {
                int val=in();
                pre[now]=val;
                now=val;
            }
        }
        int i=1;
        while(pre[i]==i+1) i++;    //开始已经有多少玩具嵌套好了
        int ans=0;
        for(;i<=n;i++)
        {
    
            while(pre[i]==i && i<=n)  i++,ans++;  //该玩具是单独的一个，把前面的嵌套进去
    
            int x=i,j;
            bool have=0;
            while(x<=n && pre[x]!=x )      //该玩具被嵌套，把嵌套的玩具一个个拿出来
            {
                j=pre[x];
                pre[x]=x;   //嵌套自己表示拆开了单独一个
                x=j;
                ans++;       //每拆一次加一
                have=1;
    
            }
            if(have) ans++;  //拆开了之后把它嵌套上
    
        }
        cout<<ans-1<<endl;  //开始第一个也算了，所以减一
        return 0;
    }