제출 #95013

#제출 시각아이디문제언어결과실행 시간메모리
95013PusheenRima (COCI17_rima)C++11
70 / 140
520 ms250564 KiB
#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; } bool end[26]; node* ch[26]; }; bool cmp(string& s1, string& s2) { return s1.size() < s2.size(); } string arr[MAXN]; int ans = 0; int dfs(node* curr, node* par) { bool hasC = false; int cAns = 0; pi gre{0,0}; F0R(i, 26) { if(curr->ch[i]) { int cVal = dfs(curr->ch[i], curr); if(curr->end[i]) { MAX(cAns, cVal); if (cVal > gre.s) { gre.s = cVal; if (gre.s > gre.f) swap(gre.s, gre.f); } } hasC = true; } } if(curr->val) MAX(ans, gre.f + gre.s + curr->val); if(!hasC) { return curr->val; } return (curr->val == 0 ? 0 : curr->val+cAns); } 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(); if(!j) { curr->val++; curr->end[arr[i][j]-'a'] = true; } curr = curr->ch[arr[i][j]-'a']; } } dfs(init, nullptr); // cout << '\n' << init->ch['i'-'a']->val << '\n'; cout << ans << '\n'; } //Remember to change MAXN if relevant!!!
#Verdict Execution timeMemoryGrader output
Fetching results...