oj.uz

Submission #973882

# Submission time Handle Problem Language Result Execution time Memory
973882 2024-05-02T12:14:30 Z sleepntsheep Savez (COCI15_savez) C
48 / 120
 1000 ms 11608 KB 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define N 500
#define TN 2000000
#define N_ (TN+N+100)
#define M (N*N*2)

char s[N_];
int p, n, z, at[N+1], hash[N_], BASE, MOD = 1000000007, head[N], nxt[M], vv[M], vis[N], dp[N];

unsigned rand_wide() { return 1llu * rand()*rand(); }
unsigned rand_wide2(unsigned l, unsigned r) { if (l==r)return l; return l+rand_wide()%(r-l); }

void link(int u, int v)
{
    static int i = 1;
    nxt[i] = head[u];
    vv[i] = v;
    head[u] = i++;
}

int power(int a,int b)
{
    if (!b)return 1;
    int r= power(a,b/2);
    if(b&1)return r*1ll*r%MOD*a%MOD;
    return r*1ll*r%MOD;
}

void dfs(int u)
{
    vis[u] = 1;
    for(int j = head[u]; j; j = nxt[j])
    {
        if (!vis[vv[j]]) dfs(vv[j]);
        if(dp[vv[j]]+1>dp[u])dp[u]=dp[vv[j]]+1;
    }
    if(dp[u]>z)z=dp[u];
}

int main()
{
    srand(time(0));
    BASE = rand_wide2(200, MOD-1);

    scanf("%d", &n);
    for (int len, i = 0; i < n; ++i)
        scanf("%s", s+(at[i]=p)), at[i+1]=p+=strlen(s+at[i])+1;

    for (int i=0;i<n;++i)
        for(int bp=1,j=at[i];s[j];++j,bp=bp*1ll*BASE%MOD)
            hash[j] = bp * 1ll * s[j]%MOD;

    for (int i=1;i<=at[n];++i)
        if(s[i]>0) hash[i]=(hash[i]+hash[i-1])%MOD;

    for (int i = 0; i < n; ++i)
    {
        int hash_i=hash[at[i+1]-2];
        for (int j = i + 1; j < n; ++j)
        {
            int leni=at[i+1]-at[i]-1,lenj=at[j+1]-at[j]-1;
            if(leni>lenj)continue;
            if(hash_i==hash[at[j]+leni-1]&&
                    hash_i*1ll*power(BASE,lenj-leni)%MOD==(hash[at[j+1]-2]+MOD-hash[at[j+1]-2-leni])%MOD)
                link(i, j);
        }
    }

    for (int i=0;i<n;++i)if(!vis[i])dfs(i);
    printf("%d",z+1);

}

Compilation message

savez.c: In function 'main':
savez.c:50:14: warning: unused variable 'len' [-Wunused-variable]
   50 |     for (int len, i = 0; i < n; ++i)
      |              ^~~
savez.c:49:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
savez.c:51:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%s", s+(at[i]=p)), at[i+1]=p+=strlen(s+at[i])+1;
      |         ^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 10944 KB Output is correct
2 Correct 25 ms 10920 KB Output is correct
3 Correct 35 ms 11092 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 40 ms 11012 KB Output is correct
3 Correct 31 ms 10844 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 11608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 11556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 7764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 7712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 7516 KB Time limit exceeded
2 Halted 0 ms 0 KB -