제출 #885041

#제출 시각아이디문제언어결과실행 시간메모리
885041patrikpavic2회문 (APIO14_palindrome)C++17
8 / 100
1054 ms1248 KiB
#include <algorithm> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #define PB push_back using namespace std; typedef long long ll; const int N = 3e5 + 500; const int INF = 0x3f3f3f3f; const int ALP = 26; struct node{ node *ch[ALP], *bk; int len, cnt; node() { len = 0, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch)); } node(int _len) { node(); len = _len; } }; node *n0, *n1; vector < node* > v; node* create_eertree(string &s){ n0 = new node(0); n1 = new node(-1); n0->bk = n1; n1->bk = n1; node* cur = n0; for(int i = 0;i < (int)s.size();i++){ for(;cur->len+1>i||s[i-cur->len-1]!=s[i];cur=cur->bk); node *rmb = cur->bk; if(!cur->ch[s[i] - 'a']) cur->ch[s[i] - 'a'] = new node(cur->len + 2), v.PB(cur->ch[s[i] - 'a']); cur = cur->ch[s[i] - 'a']; cur->cnt++; for(;rmb->len+1>i||s[i-rmb->len-1]!=s[i];rmb=rmb->bk); if(cur->len == 1) cur->bk = n0; else{ if(!rmb->ch[s[i] - 'a']) rmb->ch[s[i] - 'a'] = new node(rmb->len + 2), v.PB(rmb->ch[s[i] - 'a']); cur->bk = rmb->ch[s[i] - 'a']; } } return n0; } bool cmp(node* X, node* Y){ return X->len > Y->len; } string s; void dfs(node* x) { if(!x) return; v.PB(x); for(int i = 0;i < 26;i++) if(x->ch[i]) dfs(x->ch[i]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> s; ll mx = 0; node* root = create_eertree(s); //dfs(root); dfs(root->bk); sort(v.begin(), v.end(), cmp); for(int i = 0;i < (int)v.size();i++){ mx = max(mx, (ll)v[i]->len * v[i]->cnt); v[i]->bk->cnt += v[i]->cnt; } cout << mx << endl; }

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int main()':
palindrome.cpp:70:11: warning: unused variable 'root' [-Wunused-variable]
   70 |     node* root = create_eertree(s);
      |           ^~~~
#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...