Submission #5675183
Source Code Expand
#include<bits/stdc++.h> #define ll long long int using namespace std; const int MAXN = 205000; struct node { int next[26]; int len; int sufflink; int num; }; ll len; string s; node tree[MAXN]; int num; // node 1 - root with len -1, node 2 - root with len 0 int suff; // max suffix palindrome long long ans; bool addLetter(int pos) { int cur = suff, curlen = 0; int let = s[pos] - 'a'; while (true) { curlen = tree[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break; cur = tree[cur].sufflink; } if (tree[cur].next[let]) { suff = tree[cur].next[let]; return false; } num++; suff = num; tree[num].len = tree[cur].len + 2; tree[cur].next[let] = num; if (tree[num].len == 1) { tree[num].sufflink = 2; tree[num].num = 1; return true; } while (true) { cur = tree[cur].sufflink; curlen = tree[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { tree[num].sufflink = tree[cur].next[let]; break; } } tree[num].num = 1 + tree[tree[num].sufflink].num; return true; } void initTree() { num = 2; suff = 2; tree[1].len = -1; tree[1].sufflink = 1; tree[2].len = 0; tree[2].sufflink = 1; } int main() { //assert(freopen("input.txt", "r", stdin)); //assert(freopen("output.txt", "w", stdout)); cin>>s; len = s.length(); initTree(); for (int i = 0; i < len; i++) { addLetter(i); ans += tree[suff].num; } ans = ((len)*(len+1))/2LL - ans; cout << ans + 1<< endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Reverse and Compare |
User | vjudge3 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1751 Byte |
Status | WA |
Exec Time | 16 ms |
Memory | 23172 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | WA | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 14 ms | 23172 KB |
subtask_1_03.txt | AC | 1 ms | 256 KB |
subtask_1_04.txt | AC | 1 ms | 256 KB |
subtask_1_05.txt | WA | 1 ms | 256 KB |
subtask_1_06.txt | WA | 1 ms | 256 KB |
subtask_1_07.txt | WA | 2 ms | 384 KB |
subtask_1_08.txt | WA | 10 ms | 772 KB |
subtask_1_09.txt | WA | 11 ms | 900 KB |
subtask_1_10.txt | WA | 11 ms | 772 KB |
subtask_1_11.txt | WA | 10 ms | 772 KB |
subtask_1_12.txt | WA | 11 ms | 900 KB |
subtask_1_13.txt | WA | 11 ms | 900 KB |
subtask_1_14.txt | AC | 16 ms | 23172 KB |
subtask_1_15.txt | AC | 15 ms | 23172 KB |
subtask_1_16.txt | AC | 16 ms | 23172 KB |
subtask_1_17.txt | AC | 15 ms | 23172 KB |