제출 #94834

#제출 시각아이디문제언어결과실행 시간메모리
94834quoriessRima (COCI17_rima)C++14
56 / 140
489 ms150460 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int lli; typedef pair<lli,lli> pii; #define dbg(x) //cout<<#x<<" has a value of: "<<x<<"\n"; #define usize(x) (int)(x.size()) #define plist(x) for(int i=0;i<usize(x);i++)cout<<"eleman "<<i<<" = "<<x[i]<<"\n"; #define foreach(x) for(auto item:x) #define fill(s,x) for(int i=0;i<x;i++)cin>>s[i]; #define in(veriler,a) (veriler.find(a)!=veriler.end()) #define btw(x,y,z) x>=y && x<=z #define ord(x) x-'a' std::ostream& operator<<(std::ostream& os, pair<int,int> p) { os << p.first << ", " << p.second; return os; } const int ALPHABET_SIZE=26; struct TrieNode{ TrieNode* children[ALPHABET_SIZE]; int isEndSy; int dp; }; TrieNode* mkTrieNode(){ TrieNode* pnode=new TrieNode; pnode->isEndSy=0; for (int i = 0; i < ALPHABET_SIZE; i++) { pnode->children[i]=NULL; } return pnode; } void addString(TrieNode* root,string str){ TrieNode* v=root; for (int i = 0; i < usize(str); i++) { if(!v->children[ord(str[i])]) v->children[ord(str[i])]=mkTrieNode(); v=v->children[ord(str[i])]; } v->isEndSy++; } int glmx=-1; void dfs(TrieNode* n){ int d=0, mxd=-1; int s=0; for (int i = 0; i < ALPHABET_SIZE; i++) { if(n->children[i]){ dbg((char)(i+'a')); dfs(n->children[i]); if(n->children[i]->isEndSy){ s+=n->children[i]->isEndSy; if(n->children[i]->dp>d){ d=n->children[i]->dp; mxd=i; } } } } if(n->isEndSy==0)return; int rn=s+d+((mxd>-1&&n->children[mxd]->isEndSy)?-n->children[mxd]->isEndSy:0); n->dp=rn+n->isEndSy; dbg(n->dp); glmx=max(glmx,n->dp); } int main(){ int n; cin>>n; vector<string> dizi; for (int i = 0; i < n; i++) { string s; cin>>s; reverse(s.begin(),s.end()); dizi.push_back(s); } sort(dizi.begin(),dizi.end()); TrieNode* root=mkTrieNode(); foreach(dizi){ addString(root,item); } dfs(root); cout<<glmx<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...