Submission #1258766
Source Code Expand
#include<bits/stdc++.h>
#define ALL(X) X.begin(),X.end()
#define FOR(I,A,B) for(int (I) = (A); (I) <= (B); (I)++)
#define FORW(I,A,B) for(int (I) = (A); (I) < (B); (I)++)
#define FORD(I,A,B) for(int (I) = (A); (I) >= (B); (I)--)
#define CLEAR(X) memset(X,0,sizeof(X))
#define SIZE(X) int(X.size())
#define CONTAINS(A,X) (A.find(X) != A.end())
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#ifdef LOCAL
#define D(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define D(...) ;
#define cerr if(0)cout
#endif
using namespace std;
template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U> &_p) { return os << "(" << _p.X << "," << _p.Y << ")"; }
template<typename T> ostream& operator << (ostream &os, const vector<T>& _V) { bool f = true; os << "["; for(auto v: _V) { os << (f ? "" : ",") << v; f = false; } return os << "]"; }
template<typename T> ostream& operator << (ostream &os, const set<T>& _S) { bool f = true; os << "("; for(auto s: _S) { os << (f ? "" : ",") << s; f = false; } return os << ")"; }
template<typename T, typename U> ostream& operator << (ostream &os, const map<T, U>& _M) { return os << set<pair<T, U>>(ALL(_M)); }
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<", "; _dbg(sdbg+1, a...); }
typedef signed long long slong;
typedef long double ldouble;
const slong INF = 1000000100;
const ldouble EPS = 1e-9;
#define fpos adla
const int SIGMA = 26;
const int OFFSET = 'a';
const int inf = 1e9;
const int MAXN = 2e5+2;
char s[MAXN];
int G[MAXN][SIGMA];
int len[MAXN], fpos[MAXN], link[MAXN];
int node, pos, sz, n;
void init() {
sz = 1;
// n = node = pos = 0;
// CLEAR(G), CLEAR(len), CLEAR(fpos); CLEAR(link);
// CLEAR(s);
len[0] = inf;
}
int make_node(int _pos, int _len) {
fpos[sz] = _pos;
len[sz] = _len;
return sz++;
}
void go_edge() {
while(pos > len[G[node][s[n - pos]]]) {
node = G[node][s[n - pos]];
pos -= len[node];
}
}
void add_letter(int c) {
c -= 'a';
s[n++] = c;
pos++;
int last = 0;
while(pos > 0) {
go_edge();
int edge = s[n - pos];
int &v = G[node][edge];
int t = s[fpos[v] + pos - 1];
if(v == 0) {
v = make_node(n - pos, inf);
link[last] = node;
last = 0;
} else if(t == c) {
link[last] = node;
return;
} else {
int u = make_node(fpos[v], pos - 1);
G[u][c] = make_node(n - 1, inf);
G[u][t] = v;
fpos[v] += pos - 1;
len[v] -= pos - 1;
v = u;
link[last] = u;
last = u;
}
if(node == 0) {
pos--;
} else {
node = link[node];
}
}
}
int length(int v) {
return min(n - fpos[v], len[v]);
}
inline slong f(slong x) {
return x * (x + 1) / 2;
}
inline slong f(slong a, slong b) {
return f(a) - f(b-1);
}
slong result;
void dfs(int v, slong old_d, slong d) {
if(v != 0) result += f(d) - f(old_d);
FORW(c,0,SIGMA) if(G[v][c] != 0) {
int u = G[v][c];
dfs(u, d, d + length(u));
}
}
void solve() {
init();
string s;
cin >> s;
for(char c: s) add_letter(c);
result = 0;
dfs(0, 0, 0);
cout << result << endl;
}
int main() {
ios_base::sync_with_stdio(false);
solve();
}
Submission Info
Submission Time |
|
Task |
E - 部分文字列 |
User |
pmichalak |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3742 Byte |
Status |
AC |
Exec Time |
18 ms |
Memory |
16336 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
15 / 15 |
35 / 35 |
50 / 50 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt, sample_3.txt |
Subtask1 |
sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt |
Subtask2 |
sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt |
Subtask3 |
sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_1.txt |
AC |
2 ms |
2304 KB |
sample_2.txt |
AC |
2 ms |
2304 KB |
sample_3.txt |
AC |
2 ms |
2304 KB |
sub1_1.txt |
AC |
2 ms |
2304 KB |
sub1_2.txt |
AC |
2 ms |
2304 KB |
sub1_3.txt |
AC |
2 ms |
2304 KB |
sub1_4.txt |
AC |
2 ms |
2304 KB |
sub1_5.txt |
AC |
2 ms |
2304 KB |
sub1_6.txt |
AC |
2 ms |
2304 KB |
sub1_7.txt |
AC |
2 ms |
2304 KB |
sub1_8.txt |
AC |
2 ms |
2304 KB |
sub1_9.txt |
AC |
2 ms |
2304 KB |
sub2_1.txt |
AC |
2 ms |
2304 KB |
sub2_2.txt |
AC |
2 ms |
2304 KB |
sub3_1.txt |
AC |
2 ms |
2432 KB |
sub3_2.txt |
AC |
4 ms |
4736 KB |
sub3_3.txt |
AC |
18 ms |
16336 KB |