Submission #65792

#TimeUsernameProblemLanguageResultExecution timeMemory
65792forestryksSavez (COCI15_savez)C++14
0 / 120
63 ms27112 KiB
/////////////////////////////////////////////////////////////////////////////////////////////// #include <bits/stdc++.h> using namespace std; // #define int long long #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout) #define f first #define s second #define x1 x1qwer #define y1 y1qwer #define right right123 #define left left123 #define foreach(it, v) for (auto it : v) #define rep(it, n) for (int it = 0; it < n; ++it) #define forin(it, l, r) for (int it = l; it < r; ++it) #define all(x) x.begin(), x.end() typedef long long ll; typedef unsigned long long ull; typedef double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const double DINF = numeric_limits<double>::infinity(); const ll MOD = 1e9 + 7; const double EPS = 1e-7; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } mt19937 mmtw_(MOD); uniform_int_distribution<ll> rd_; ll randomll() { return rd_(mmtw_);} ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; } template <class T> T fact(T n) { if (n == 1) return 1; return n * fact(n - 1); } //////////////////////////////////////////////////////////////////////////////////////////////// struct MyMap : vector<pair<int, int>> { int& operator[](const int v) { auto it = lower_bound(this->begin(), this->end(), make_pair(v, -1)); if (it != this->end() && it->first == v) { return it->second; } return this->insert(it, {v, 0})->second; } }; const int MAXN = 1e6 + 5; int n; int last = 1; // map<int, int> to[MAXN]; MyMap to[MAXN]; int res[MAXN]; int term[MAXN]; inline int get(const string &s, int i) { return (s[i] - 'A') + (s[s.size() - 1 - i] - 'A') * 32; } void trie_add(const string &s) { int n = s.size(); int v = 0; for (int i = 0; i < n; ++i) { int ch = get(s, i); if (to[v][ch] == 0) { to[v][ch] = last++; v = last - 1; } else { v = to[v][ch]; } } term[v]++; } int dfs(int v) { res[v] = term[v]; for (auto it : to[v]) { res[v] = max(res[v], dfs(it.s) + term[v]); } return res[v]; } int main() { FAST_IO; cin >> n; rep(i, n) { string s; cin >> s; trie_add(s); } cout << dfs(0) << endl; }
#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...