Submission #973878

#TimeUsernameProblemLanguageResultExecution timeMemory
973878sleepntsheepSavez (COCI15_savez)C11
12 / 120
1084 ms15188 KiB
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> #define N 500 #define TN 3000000 #define N_ (TN+N+1) #define M (2*N) 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 (stderr)

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;
      |         ^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...