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
AC × 3
AC × 12
AC × 14
AC × 17
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