Submission #57917

#	Time	Username	Problem	Language	Result	Execution time	Memory
57917		Benq	Lozinke (COCI17_lozinke)	C++14	100 / 100	48 ms	21880 KiB

lozinke

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
 
string A[20000];
int N, ans;
 
template<int MX> struct tri {
    int trie[MX][26], nex = 0; // easily changed to character
    int sz[MX];
    bool done[MX];
    vi oc;
    
    tri() {
        memset(trie,0,sizeof trie);
    }
    
    void ins(string x, int a = 1) { // insert or delete
        int cur = 0; 
        for (char c: x) {
            int t = c-'a';
            if (!trie[cur][t]) trie[cur][t] = ++nex;
            cur = trie[cur][t];
        }
        sz[cur] += a;
    }
    
    void solve(string x) {
        int cur = 0;
        for (char c: x) {
            int t = c-'a';
            if (!trie[cur][t]) break;
            cur = trie[cur][t];
            if (!done[cur]) {
                done[cur] = 1; oc.pb(cur);
                ans += sz[cur];
            }
        }
    }
};
 
tri<200005> t;
 
void test(string x) {
    F0R(i,sz(x)) t.solve(x.substr(i,sz(x)-i));
    for (int i: t.oc) t.done[i] = 0;
    t.oc.clear();
    ans --;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    F0R(i,N) {
        // F0R(j,10) A[i] += 'a';
        cin >> A[i];
        t.ins(A[i]);
    }
    F0R(i,N) test(A[i]);
    cout << ans;
}
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 100 / 100