#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class U>
inline void MAX(T &a, U b) { if (a < b) a = b; }
template<class T, class U>
inline void MIN(T &a, U b) { if (a > b) a = b; }
template<class T, class U>
inline void MODA(T &a, U b) {
a %= b;
if (a < 0) a += b;
}
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(20)
#define dbg(x) cout << (#x) << " is " << (x) << '\n'
#define dbg2(x, y) cout << (#x) << " is " << (x) << " and " << (#y) << " is " << y << '\n'
#define dbgarr(x, sz) for(int asdf = 0; asdf < (sz); asdf++) cout << x[asdf] << ' '; cout << '\n'
#define dbgarr2(x, rose, colin) for(int asdf2 = 0; asdf2 < rose; asdf2++) { dbgarr(x[asdf2], colin); }
#define dbgitem(x) for(auto asdf = x.begin(); asdf != x.end(); asdf++) cout << *asdf << ' '; cout << '\n'
#define finish(x) return cout << (x) << '\n', 0
#define F0R(i, a) for(int (i)=0;(i)<(a);++(i))
#define FOR(i, a, b) for(int (i)=(a);(i)<(b);++(i))
#define F0Rd(i, a) for(int (i)=a;(i)>=0;--(i))
#define FORd(i, a, b) for(int (i)=a;(i)>=(b);--(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
template <typename T> ostream& operator<<(ostream& os, const vector<T> &p){os << "["; F0R(i, p.size()) os << p[i] << (i == p.size() - 1 ? "" : ",") ; os << "]"; return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}"; return os;}
template <typename T> ostream& operator<<(ostream& os, const multiset<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}"; return os;}
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U> &p){os << '{' << p.first << ',' << p.second << '}'; return os;}
#define mp make_pair
#define pb push_back
#define pf push_front
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const int NINF = -0x3f3f3f40;
const ll INF_L = 0x3f3f3f3f3f3f3f3f;
const ll NINF_L = -0x3f3f3f3f3f3f3f40;
const int MAXN = 3e6+5;
struct node {
int val;
node() {
val = 0;
F0R(i, 26) ch[i] = nullptr;
F0R(i, 26) end = false;
}
bool end;
node* ch[26];
};
bool cmp(string& s1, string& s2) {
return s1.size() < s2.size();
}
string arr[MAXN];
int ans = 0;
void dfs(node* curr) {
pi gre{0, 0};
int cSum = 0;
F0R(i, 26) {
if (curr->ch[i]) {
dfs(curr->ch[i]);
cSum += curr->ch[i]->end;
}
}
F0R(i, 26) {
if(curr->ch[i] && curr->ch[i]->end) {
MAX(curr->val, curr->ch[i]->val+cSum);
if(curr->ch[i]->val>gre.s) {
gre.s = curr->ch[i]->val;
if(gre.s>gre.f) swap(gre.s,gre.f);
}
}
}
MAX(ans, gre.f+gre.s+cSum+curr->end);
}
int main() {
FAST_IO;
int n; cin >> n;
F0R(i, n) cin >> arr[i];
sort(arr, arr + n, cmp);
node* init = new node();
F0R(i, n) {
node* curr = init;
F0Rd(j, arr[i].size() - 1) {
if(!(curr->ch[arr[i][j] - 'a']))
curr->ch[arr[i][j] - 'a'] = new node();
curr = curr->ch[arr[i][j]-'a'];
}
curr->end = true;
}
dfs(init);
// cout << '\n' << init->ch['a'-'a'] -> end << '\n';
cout << ans << '\n';
}
//Remember to change MAXN if relevant!!!
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
75 ms |
94328 KB |
Output is correct |
| 2 |
Correct |
75 ms |
94388 KB |
Output is correct |
| 3 |
Correct |
73 ms |
94328 KB |
Output is correct |
| 4 |
Correct |
464 ms |
228752 KB |
Output is correct |
| 5 |
Correct |
109 ms |
98040 KB |
Output is correct |
| 6 |
Correct |
169 ms |
175372 KB |
Output is correct |
| 7 |
Correct |
165 ms |
175132 KB |
Output is correct |
| 8 |
Correct |
178 ms |
174936 KB |
Output is correct |
| 9 |
Correct |
189 ms |
180944 KB |
Output is correct |
| 10 |
Correct |
162 ms |
174944 KB |
Output is correct |
