#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 409;
const int mod2 = 1e9 + 433;
typedef pair<int, lint> pi;
lint get_hash(string &s, int st, int ed){
lint h1 = 0;
lint h2 = 0;
for(int i=st; i<ed; i++){
h1 = h1 * 257 + s[i];
h2 = h2 * 257 + s[i];
h1 %= mod1;
h2 %= mod2;
}
return h1 * mod2 + h2;
}
int n, vtx[500005], par[500005], cst[500005];
string s[500005];
char buf[3000005];
map<pair<int, lint>, int> hsh;
vector<int> gph[500005];
int lcp(string &a, string &b){
for(int i=0; i<a.size(); i++){
if(a[i] != b[i]) return i;
}
return a.size();
}
bool vis[500005];
pi dfs(int x, int p){
vis[x] = 1;
pi ret(0, x);
for(auto &i : gph[x]){
if(i != p){
ret = max(ret, dfs(i, x));
}
}
ret.first += cst[x];
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%s", buf);
s[i] = buf;
reverse(s[i].begin(), s[i].end());
}
sort(s+1, s+n+1, [&](const string &a, const string &b){
return make_pair(a.size(), a) < make_pair(b.size(), b);
});
for(int i=1; i<=n; ){
int e = i;
while(e <= n && s[e].size() == s[i].size() && lcp(s[i], s[e]) >= s[i].size() - 1) e++;
for(int j=i; j<e; j++){
vtx[j] = i;
cst[j] = e - i;
}
i = e;
}
int ans = 0;
for(int i=1; i<=n; i++){
hsh[pi(s[i].size(), get_hash(s[i], 0, s[i].size()))] = i;
}
set<pi> st;
for(int i=1; i<=n; i++){
lint p = get_hash(s[i], 0, s[i].size() - 1);
par[i] = hsh[pi(s[i].size() - 1, p)];
if(par[i]){
int s = vtx[par[i]];
int e = vtx[i];
if(st.find(pi(s, e)) != st.end()) continue;
st.insert(pi(s, e));
gph[s].push_back(e);
gph[e].push_back(s);
}
}
int ret = 0;
for(int i=1; i<=n; i++){
if(!vis[i] && vtx[i] == i){
ret += dfs(dfs(i, -1).second, -1).first;
}
}
cout << ret << endl;
}
Compilation message
rima.cpp: In function 'int lcp(std::__cxx11::string&, std::__cxx11::string&)':
rima.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<a.size(); i++){
^
rima.cpp: In function 'int main()':
rima.cpp:61:65: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(e <= n && s[e].size() == s[i].size() && lcp(s[i], s[e]) >= s[i].size() - 1) e++;
^
rima.cpp:68:6: warning: unused variable 'ans' [-Wunused-variable]
int ans = 0;
^
rima.cpp:50:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
rima.cpp:52:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
38652 KB |
Output isn't correct |
| 2 |
Incorrect |
9 ms |
38652 KB |
Output isn't correct |
| 3 |
Incorrect |
9 ms |
38652 KB |
Output isn't correct |
| 4 |
Incorrect |
993 ms |
88020 KB |
Output isn't correct |
| 5 |
Incorrect |
66 ms |
41820 KB |
Output isn't correct |
| 6 |
Incorrect |
23 ms |
39672 KB |
Output isn't correct |
| 7 |
Incorrect |
26 ms |
39552 KB |
Output isn't correct |
| 8 |
Incorrect |
19 ms |
39468 KB |
Output isn't correct |
| 9 |
Incorrect |
133 ms |
43120 KB |
Output isn't correct |
| 10 |
Incorrect |
29 ms |
39484 KB |
Output isn't correct |
