Submission #697175

#	Time	Username	Problem	Language	Result	Execution time	Memory
697175		bin9638	Raspad (COI17_raspad)	C++17	61 / 100	6039 ms	43544 KiB

raspad

#include<bits/stdc++.h>

using namespace std;
#define N  100010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("omit-frame-pointer")
#pragma GCC optimize("unroll-loops")

int f[N],a[N][55],n,m;

struct haha
{
    int val=0,sum=0,sl=0,cnt[52]={},id[52]={},ktr[52]={};

    int get(int mod)
    {
        int res=0;
        for(int i=1;i<=m;i++)
            res=(res+f[i]%mod*id[i])%mod;
        return res;
    }

    void DFS(int u,int dem,int h)
    {
        ktr[u]=dem;
        if(ktr[u-1]==0&&a[h][u-1]==1)
            DFS(u-1,dem,h);
        if(ktr[u+1]==0&&a[h][u+1]==1)
            DFS(u+1,dem,h);
        for(int i=1;i<=m;i++)
            if(ktr[i]==0&&id[i]==id[u])
                DFS(i,dem,h);
    }

    void build(int h)
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=m;i++)
            if(id[i]!=0)
                cnt[id[i]]=1;
        int dem=m+1;
        for(int i=1;i<=m;i++)
            if(a[h][i]==0)
                id[i]=0;
                else{
                    if(id[i]==0)
                        id[i]=++dem;
                }
        for(int i=1;i<=m;i++)
            if(id[i]!=0&&id[i]<=m)
                cnt[id[i]]=0;
        for(int i=1;i<=m;i++)
            if(cnt[i]>0)
                sum+=sl;
        dem=0;
        memset(ktr,0,sizeof(ktr));
        for(int i=1;i<=m;i++)
            if(ktr[i]==0&&id[i]!=0)
            {
                dem++;
                DFS(i,dem,h);
            }
        for(int i=1;i<=m;i++)
            id[i]=ktr[i];
        val=get(1e9+8277)*1e9+get(1e9+9277);
    }

    int solve()
    {
        memset(cnt,0,sizeof(cnt));
         for(int i=1;i<=m;i++)
            if(id[i]!=0)
                cnt[id[i]]=1;
        int res=0;
        for(int i=1;i<=m;i++)
            if(cnt[i]!=0)
                res++;
        return res;
    }

    bool operator<(const haha&A)const
    {
        return val<A.val;
    }
};
vector<haha>s,luu;

int32_t main()
{
   // freopen("A.inp","r",stdin);
   // freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        s=" "+s;
        for(int j=1;j<=m;j++)
        {
            a[i][j]=(s[j]-'0');
          ///  cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
        }
    }
    for(int i=1;i<=m;i++)
        f[i]=1ll*rand()*rand()*rand();
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        s.emplace_back();
        s.back().sl=1;
        for(int j=0;j<s.size();j++)
            s[j].build(i);
        sort(s.begin(),s.end());
        luu.clear();
        while(!s.empty())
        {
            haha cc=s.back();
            s.pop_back();
            if(!s.empty()&&s.back().val==cc.val)
            {
                s.back().sum+=cc.sum;
                s.back().sl+=cc.sl;
            }else
            {
                luu.pb(cc);
            }
        }
        s=luu;
      //  if(s.size()>m)
        //    return 0;
        for(auto cc:s)
            ans+=cc.sum+cc.solve()*cc.sl;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int32_t main()':
raspad.cpp:123:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<haha>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 0 / 39