Submission #405385

#	Time	Username	Problem	Language	Result	Execution time	Memory
405385		IloveN	Languages (IOI10_languages)	C++14	0 / 100	1793 ms	253388 KiB

lang

#include<bits/stdc++.h>
#include "grader.h"

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
namespace myrand
{
    mt19937 mt(chrono::system_clock::now().time_since_epoch() / chrono::microseconds(1));
    ll Int(ll l,ll r) {return uniform_int_distribution<ll> (l,r)(mt);}
}

using namespace myrand;
const int N = 1e5 + 10;
int cnt = 0;

struct state
{
    int len, link;
    unordered_map<int, int> nxt;
};

state sa[N * 22];
int root[N], End[N], sz = 0;

void init()
{
    //for (int i = 0; i < N * 22; ++i) sa[i].nxt.max_load_factor(0.25);
    for (int i = 0; i <= 55; ++i)
    {
        root[i] = sz++;
        sa[i].link = -1;
        sa[i].len = 0;
        End[i] = i;
    }
}

void add(int id, int c)
{
    int cur = sz++;
    int p = End[id];
    End[id] = cur;
    sa[cur].len = sa[p].len + 1;
    while (p != -1 && !sa[p].nxt.count(c))
    {
        sa[p].nxt[c] = cur;
        p = sa[p].link;
    }
    if (p == -1)
    {
        sa[cur].link = root[id];
        return;
    }
    int q = sa[p].nxt[c];
    if (sa[p].len + 1 == sa[q].len)
    {
        sa[cur].link = q;
        return;
    }
    int clone = sz++;
    sa[clone].len = sa[p].len + 1;
    sa[clone].nxt = sa[q].nxt;
    sa[clone].link = sa[q].link;
    while (p != -1 && sa[p].nxt[c] == q)
    {
        sa[p].nxt[c] = clone;
        p = sa[p].link;
    }
    sa[cur].link = sa[q].link = clone;
}

void excerpt(int E[])
{
    ll id = 0, mx = -1;
    for (int i = 0; i <= 55; ++i)
    {
        ll score = 0;
        int cur = root[i];
        for (int j = 0; j < 100; ++j)
        {
            int r = j;
            if (!sa[cur].nxt.count(E[j])) continue;
            while (r < 100 && sa[cur].nxt.count(E[r]))
                cur = sa[cur].nxt[E[r++]];
            score += (r - j) * (r - j);
            j = r - 1;
        }
        if (score > mx) id = i, mx = score;
    }
    id = language(id);
    if (cnt == 0) init();
    cnt++;
    //if (cnt > 8e3) return;
    for (int i = 0; i < 50; ++i) add(id, E[i]);
    add(id, 0);
}

/*int main()
{
    //freopen("ss.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}*/

• Subtask 1: 0 / 30
• Subtask 2: 0 / 80