oj.uz

Submission #697178

# Submission time Handle Problem Language Result Execution time Memory
697178 2023-02-08T17:30:47 Z bin9638 Raspad (COI17_raspad) C++17
61 / 100
 6000 ms 44048 KB 
#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);
    }

    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]=rand()%2;
            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;
        for(auto cc:s)
            ans+=cc.sum+cc.solve()*cc.sl;
    }
    cout<<ans;
    return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 3 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 34 ms 852 KB Output is correct
10 Correct 12 ms 720 KB Output is correct
11 Correct 22 ms 724 KB Output is correct
12 Correct 29 ms 824 KB Output is correct
13 Correct 31 ms 724 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 22356 KB Output is correct
2 Correct 259 ms 43888 KB Output is correct
3 Correct 505 ms 43852 KB Output is correct
4 Correct 133 ms 39576 KB Output is correct
5 Correct 75 ms 13724 KB Output is correct
6 Correct 297 ms 43900 KB Output is correct
7 Correct 441 ms 43852 KB Output is correct
8 Correct 238 ms 35336 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 34 ms 852 KB Output is correct
10 Correct 12 ms 720 KB Output is correct
11 Correct 22 ms 724 KB Output is correct
12 Correct 29 ms 824 KB Output is correct
13 Correct 31 ms 724 KB Output is correct
14 Correct 88 ms 22356 KB Output is correct
15 Correct 259 ms 43888 KB Output is correct
16 Correct 505 ms 43852 KB Output is correct
17 Correct 133 ms 39576 KB Output is correct
18 Correct 75 ms 13724 KB Output is correct
19 Correct 297 ms 43900 KB Output is correct
20 Correct 441 ms 43852 KB Output is correct
21 Correct 238 ms 35336 KB Output is correct
22 Correct 778 ms 35304 KB Output is correct
23 Correct 3895 ms 43932 KB Output is correct
24 Correct 3688 ms 44048 KB Output is correct
25 Correct 810 ms 43908 KB Output is correct
26 Correct 920 ms 43896 KB Output is correct
27 Correct 1054 ms 43852 KB Output is correct
28 Correct 2658 ms 43928 KB Output is correct
29 Correct 1573 ms 43904 KB Output is correct
30 Correct 579 ms 43884 KB Output is correct
31 Execution timed out 6010 ms 43996 KB Time limit exceeded
32 Halted 0 ms 0 KB -