| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 167796 |
2019-12-10T07:35:58 Z |
egekabas |
Rima (COCI17_rima) |
C++14 |
|
471 ms |
79708 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n;
string str;
int edge[3000000][30];
int part[3000000];
int full[3000000];
int dp[3000000];
int cur = 2;
int ans;
int go(int root, char c){
int tmp = (int)(c - 'a');
if(edge[root][tmp] != 0)
return edge[root][tmp];
return edge[root][tmp] = cur++;
}
void add(string s){
int root = 1;
for(int i = 0; i < s.size(); ++i){
root = go(root, s[i]);
if(i == s.size()-2 || (i == 0 && s.size() == 1))
part[root]++;
if(i == s.size()-1)
full[root]++;
}
}
int f2(int root){
if(part[root] == 0)
return 0;
if(dp[root] != 0)
return dp[root];
dp[root] += part[root];
vector<int> v;
for(int i = 0; i <= 'z'-'a'; ++i){
if(edge[root][i] != 0){
if(full[edge[root][i]] > 0)
v.pb(f2(edge[root][i]));
}
}
sort(v.begin(), v.end(), greater<int>());
dp[root] += v[0];
if(v.size() > 1)
dp[root] += v[1];
ans = max(ans, dp[root]);
return dp[root];
}
void f1(int root){
f2(root);
for(int i = 0; i <= 'z'-'a'; ++i){
if(edge[root][i] != 0)
f1(edge[root][i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(int i = 0; i < n; ++i){
cin >> str;
reverse(str.begin(), str.end());
add(str);
}
f1(1);
cout << ans << "\n";
}
Compilation message
rima.cpp: In function 'void add(std::__cxx11::string)':
rima.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < s.size(); ++i){
~~^~~~~~~~~~
rima.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()-2 || (i == 0 && s.size() == 1))
~~^~~~~~~~~~~~~
rima.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()-1)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
471 ms |
79708 KB |
Output isn't correct |
| 5 |
Correct |
28 ms |
760 KB |
Output is correct |
| 6 |
Runtime error |
114 ms |
73316 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
112 ms |
73328 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Incorrect |
76 ms |
45616 KB |
Output isn't correct |
| 9 |
Incorrect |
101 ms |
47320 KB |
Output isn't correct |
| 10 |
Incorrect |
76 ms |
45652 KB |
Output isn't correct |
