제출 #1129579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129579		12345678	Lozinke (COCI17_lozinke)	C++17	100 / 100	34 ms	31560 KiB

lozinke

#include <bits/stdc++.h>

using namespace std;

const int nx=2e4+5, kx=26;

int n, c[nx][11], sz[nx], res;
string s;

struct node
{
    int vs, cnt;
    node* nxt[kx];
    node()
    {
        vs=cnt=0;
        for (int i=0; i<kx; i++) nxt[i]=0;
    }
};
typedef node* pnode;

pnode rt=new node();
queue<pnode> q;

void search(pnode cur, int i, int idx)
{
    if (idx>sz[i]||!(cur->nxt[c[i][idx]])) return;
    cur=cur->nxt[c[i][idx]];
    if (cur->cnt&&!cur->vs) cur->vs=1, q.push(cur), res+=cur->cnt;
    search(cur, i, idx+1);
}

void add(pnode &cur, int i, int idx)
{
    if (idx>sz[i]) return cur->cnt++, void();
    if (!(cur->nxt[c[i][idx]])) cur->nxt[c[i][idx]]=new node();
    add(cur->nxt[c[i][idx]], i, idx+1);
}

void show(pnode cur, int dpt)
{
    cout<<"debug "<<dpt<<'\n';
    for (int i=0; i<kx; i++) if (cur->nxt[i]) cout<<"move "<<i+'a'<<'\n', show(cur->nxt[i], dpt+1);
}
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>s;
        sz[i]=s.size();
        for (int j=1; j<=sz[i]; j++) c[i][j]=s[j-1]-'a';
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=sz[i]; j++) search(rt, i, j);
        while (!q.empty()) q.front()->vs=0, q.pop();
        add(rt, i, 1);
        //show(rt, 0);
    }
    rt=new node();
    for (int i=n; i>=1; i--)
    {
        for (int j=1; j<=sz[i]; j++) search(rt, i, j);
        while (!q.empty()) q.front()->vs=0, q.pop();
        add(rt, i, 1);
    }
    cout<<res;
}

• Subtask 1: 100 / 100