| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 534071 |
2022-03-08T00:19:20 Z |
colazcy |
Rima (COCI17_rima) |
C++17 |
|
1000 ms |
65828 KB |
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <vector>
#include <stack>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ull = unsigned long long;
constexpr int maxn = 5e5 + 10,maxm = 3e6 + maxn + 100,base = 131;
bool vis[maxn];
int siz[maxn],mem[maxn];
std::vector<int> G[maxn];
int dp(const int u){
if(vis[u])return mem[u];
// debug("siz[%d] = %d\n",u,siz[u]);
vis[u] = true;
int res = 0;
for(let v : G[u])
res = std::max(res,siz[u] + dp(v));
return mem[u] = res + siz[u];
}
namespace tarjan{
std::vector<int> G[maxn];
void addedge(const int u,const int v){
// debug("%d %d\n",u,v);
G[u].push_back(v);}
bool instk[maxn];
int dfn[maxn],scc[maxn],scc_tot,dfs_tot;
std::stack<int> stk;
int tarjan(const int u){
int low = dfn[u] = ++dfs_tot;
stk.push(u); instk[u] = true;
for(let v : G[u])
if(!dfn[v])low = std::min(low,tarjan(v));
else if(instk[v])low = std::min(low,dfn[v]);
if(low == dfn[u]){
scc_tot++;
int t;
do{
t = stk.top(); stk.pop(),instk[t] = false;
scc[t] = scc_tot;
siz[scc_tot]++;
}while(t != u);
}
return low;
}
}
int n,len[maxn];
char buf[maxm],*now = buf,*str[maxn];
std::vector<std::pair<ull,int>> vec;
int find(const ull x){
let it = std::lower_bound(vec.begin(),vec.end(),std::make_pair(x,0));
if(it != vec.end() && it->first == x)return it->second;
return -1;
}
int main(){
// std::freopen("rima.in","r",stdin);
// std::freopen("rima.out","w",stdout);
std::scanf("%d",&n);
rep(i,1,n){
str[i] = now;
std::scanf("%s",str[i]);
len[i] = std::strlen(str[i]);
now += len[i] + 1;
std::reverse(str[i],str[i] + len[i]);
}
rep(id,1,n){
ull h = 0;
for(int i = 0;i < len[id];i++)h = h * base + str[id][i];
vec.emplace_back(h,id);
}
std::sort(vec.begin(),vec.end());
rep(id,1,n){
ull h = 0;
for(int i = 0;i < len[id] - 1;i++)h = h * base + str[id][i];
let t = find(h);
if(t != -1)tarjan::addedge(id,t);
rep(c,'a','z'){
let t = find(h * base + c);
if(t != -1)tarjan::addedge(id,t);
}
h = h * base + str[id][len[id] - 1];
rep(c,'a','z'){
let t = find(h * base + c);
if(t != -1)tarjan::addedge(id,t);
}
}
rep(i,1,n)
if(!tarjan::dfn[i])tarjan::tarjan(i);
rep(u,1,n)
for(let v : tarjan::G[u])
if(tarjan::scc[u] != tarjan::scc[v])
G[u].push_back(v);
int ans = 0;
// debug("%d\n",tarjan::scc_tot);
rep(i,1,tarjan::scc_tot)
ans = std::max(ans,dp(i));
std::printf("%d\n",ans);
// rep(i,1,n)debug("%s\n",str[i]);
std::fclose(stdin);
std::fclose(stdout);
return 0;
}
Compilation message
rima.cpp: In function 'int main()':
rima.cpp:65:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | std::scanf("%d",&n);
| ~~~~~~~~~~^~~~~~~~~
rima.cpp:68:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | std::scanf("%s",str[i]);
| ~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23840 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23800 KB |
Output is correct |
| 4 |
Execution timed out |
1080 ms |
65828 KB |
Time limit exceeded |
| 5 |
Correct |
41 ms |
29632 KB |
Output is correct |
| 6 |
Incorrect |
22 ms |
25292 KB |
Output isn't correct |
| 7 |
Incorrect |
23 ms |
24956 KB |
Output isn't correct |
| 8 |
Incorrect |
19 ms |
24672 KB |
Output isn't correct |
| 9 |
Incorrect |
77 ms |
31704 KB |
Output isn't correct |
| 10 |
Incorrect |
17 ms |
24780 KB |
Output isn't correct |
