QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628642#7780. Dark LaTeX vs. Light LaTeXHirroAC ✓499ms299268kbC++203.2kb2024-10-10 21:24:062024-11-25 21:17:05

Judging History

你现在查看的是最新测评结果

  • [2024-11-25 21:17:05]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:499ms
  • 内存:299268kb
  • [2024-11-25 20:53:52]
  • hack成功,自动添加数据
  • (/hack/1258)
  • [2024-10-10 21:24:08]
  • 评测
  • 测评结果:100
  • 用时:539ms
  • 内存:299072kb
  • [2024-10-10 21:24:06]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long  LL;
using namespace std;
const int N = 5005;
int lcp[N][N];
int n,m;
vector<int> e[N*2];
int tot = 1, np = 1;
int fa[N * 2] = { 0 }, ch[N * 2][27] = { 0 }, len[N * 2] = { 0 }, cnt[N * 2] = { 0 };
int F[N * 2] = { 0 }, s[N * 2] = { 0 }, sp = 0;
class SAM {
public:
    void extend(int c) {
        int p = np; np = ++tot;
        len[np] = len[p] + 1; 
        cnt[np] = 1;
        for (; p && !ch[p][c]; p = fa[p])ch[p][c] = np;
        if (p == 0)fa[np] = 1;
        else {
            int q = ch[p][c];
            if (len[q] == len[p] + 1)fa[np] = q;
            else {
                int nq = ++tot;
                len[nq] = len[p] + 1;
                fa[nq] = fa[q]; fa[q] = nq; fa[np] = nq;
                for (; p && ch[p][c] == q; p = fa[p])ch[p][c] = nq;
                memcpy(ch[nq], ch[q], sizeof(ch[q]));
            }
        }
    }
    void dfs(int u) {
        for (auto& v : e[u]) {
            dfs(v);
            cnt[u] += cnt[v];
        }
    }
    void create(string& a) {
        for (int i = 0; i < (int)a.size(); i++)extend(a[i] - 'a');
        for (int i = 2; i <= tot; i++)e[fa[i]].push_back(i);
        for (int i = tot; i >= 1; i--)F[i] = i;
        dfs(1);
    }
    int find(int u) {
        if (u == F[u])return u;
        return F[u] = find(F[u]);
    }
    void tarjan(int u) {
        for (auto v : e[u]) {
            tarjan(v);
            F[v] = u;
        }
        if (e[u].size() == 0) {
            for (int i = 1; i <= sp; i++)lcp[n - len[u] + 1][n - len[s[i]] + 1] = len[find(s[i])];
            s[++sp] = u;
        }
    }
    void init() {
        for (int i = 1; i <= tot; i++) {
            fa[i] = len[i] = cnt[i] = 0;
            e[i].clear();
            memset(ch[i], 0, sizeof(ch[i]));
        }
        tot = 1, np = 1;
        sp = 0;
    }
}SAM;
LL dp[N][N],cmo=0;
LL ans = 0;
void solve(string& a,string& b) {
    SAM.init();
    n = a.size(); m = b.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            lcp[i][j] = 0;
            dp[i][j] = 0;
        }
    }
    SAM.create(b);
    for (int i = 0; i < n; i++) {
        int p = 1;
        for (int j = i; j < n; j++) {
            if (ch[p][a[j] - 'a'])p = ch[p][a[j] - 'a'];
            else break;
            dp[i][j] = cnt[p];
        }
    }
    SAM.init();
    string t = a+'{';
    reverse(t.begin(),t.end());
    SAM.create(t);
    SAM.tarjan(1);
    for (int i = 0; i < n; i++)for (int j = i + 2; j < n; j++)lcp[i][j] = min(j - i - 1, max(lcp[i][j], lcp[j][i]));
    if(!cmo)
    for (int i = 0; i < n; i++)for (int j = i; j < n; j++)ans += dp[i][j];
    cmo = 1;
    for (int j = 0; j < n; j++)for (int i = 1; i <= j; i++)dp[i][j] += dp[i - 1][j];
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j < n; j++) {//add i+1...j-1,i+2...j-1,..,i+lcp[i][j]-1...j-1
            ans += dp[i + lcp[i][j]][j - 1] - dp[i][j - 1];
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string a, b;
    cin >> a>>b;
    solve(a, b);
    solve(b, a);
    cout << ans << '\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7684kb

input:

abab
ab

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5856kb

input:

abab
abaaab

output:

29

result:

ok 1 number(s): "29"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7948kb

input:

abcd
abcde

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 0ms
memory: 5652kb

input:

aaba
ba

output:

6

result:

ok 1 number(s): "6"

Test #5:

score: 0
Accepted
time: 0ms
memory: 7824kb

input:

babababaaabbaabababbbaabbbababbaaaaa
aaaabbaababbab

output:

1161

result:

ok 1 number(s): "1161"

Test #6:

score: 0
Accepted
time: 439ms
memory: 299136kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

78156256250000

result:

ok 1 number(s): "78156256250000"

Test #7:

score: 0
Accepted
time: 8ms
memory: 65488kb

input:

gzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggzggzgzggzggzgzggzgzggz...

output:

60716448

result:

ok 1 number(s): "60716448"

Test #8:

score: 0
Accepted
time: 8ms
memory: 65352kb

input:

mlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllmllmlmllmllmlmllmlmllmllmlmllmlmllml...

output:

60679828

result:

ok 1 number(s): "60679828"

Test #9:

score: 0
Accepted
time: 498ms
memory: 298856kb

input:

vbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvbbvbvbbvbbvbvbbvbvbbvb...

output:

2655796915

result:

ok 1 number(s): "2655796915"

Test #10:

score: 0
Accepted
time: 474ms
memory: 299044kb

input:

ttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdtdttdttdtdttdttdtdttdtdttdttdtdttdttdt...

output:

2652657341

result:

ok 1 number(s): "2652657341"

Test #11:

score: 0
Accepted
time: 482ms
memory: 299012kb

input:

uupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupupuupuupupuupuupupuupupuupuupupuupuupupuupu...

output:

2619083676

result:

ok 1 number(s): "2619083676"

Test #12:

score: 0
Accepted
time: 11ms
memory: 66012kb

input:

ggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxgxggxgxggxggxgxggxggxgxggxgxggxggxg...

output:

61227979

result:

ok 1 number(s): "61227979"

Test #13:

score: 0
Accepted
time: 156ms
memory: 166956kb

input:

cwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwcwwcwwcwcwwcwwcwcw...

output:

834307544

result:

ok 1 number(s): "834307544"

Test #14:

score: 0
Accepted
time: 499ms
memory: 298816kb

input:

trtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtrttrttrtrttrtrttrttrtr...

output:

2663862697

result:

ok 1 number(s): "2663862697"

Test #15:

score: 0
Accepted
time: 6ms
memory: 63992kb

input:

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

0

result:

ok 1 number(s): "0"

Test #16:

score: 0
Accepted
time: 376ms
memory: 298796kb

input:

igkkcgocckgoocioiiggcgkigoggkociciigokikkcogkoookkiioikockoigokigiiciikcokoockgiiiogicgkkgoiogcggcgckgikccgcckoocgggogiccgkgcoccckgiooiogckoioiioogiicogkckgiickooiockogkoikogkkociioigocoiioccggkigciigcckkggiccciiiggkcgggcokookogiokoccccgogkcigokkckccoccgkoogokogkcioockkikigokiikkkoikiigckkooioogioio...

output:

1707132

result:

ok 1 number(s): "1707132"

Test #17:

score: 0
Accepted
time: 9ms
memory: 66148kb

input:

jkkkjjjkjkkkjjjjkkkkkjjjjjjkjjjjkjjjkkkjkjkkkkjjkkjjjkjkjjjkkkkjkjjkkkkkkkjkkkjkkjkkjjkkjjkjjjkkkjkjjkjkjjjjkkjjjjjjkkjjjkkkjkjkkkkkjkjjkjjkkkkkkkkjkkkjjkjjkkkjkjjkjjkkjjkkkkkjjjjjjkjjjkkjkjjkjjjkjkkjkjkkkkjjkkjkkjkkkjkkkkkkkjkjjkkjkjjkjkkkkkkkjkkjkkkkjkjkkkkkkkjkkjjkjjjkjjkkkkjkjkkjjjjjkjkjjjjkjkkk...

output:

2954810

result:

ok 1 number(s): "2954810"

Test #18:

score: 0
Accepted
time: 11ms
memory: 65788kb

input:

juxqlncuflculraueufcupffalouceftcepluhuupphohougacfftcrouohhnxopoguocjlpqpgppuhllpsnllqnftprunnucfcucclcplxuatfxtnljnuxnhapanlrpuexuflusncrapcrqpoganppxlloougftptxutfcrgchspahqghstuuefntfuauohlxlenpujeupuucnljxuunanustpuppllelnjcupqppaorpexophphnaopsxajtonupocuuoffpuqagutpuntfloalhrffhlrltghulpuoqop...

output:

40401

result:

ok 1 number(s): "40401"

Test #19:

score: 0
Accepted
time: 367ms
memory: 298764kb

input:

lmvbtqzhgzztvlsvzdesvgefvzkqfbvszmqjsgthnmhtifhztvhihdvgeqmhvzzqmqjhdmmteshvjbgvsfzgkivmvggvzbvzlemnmqhvqfmkmvmqhfqeehqvkgsedzmgbheeielzqzqtfzzvvjfievbzhdkfivhksmzbegkzsilnzgnzbqeqtghdzljvvfedmkeivmnzznhfhekvzeqvvfvqzehdhvsmklbzhhfzdtzqlmhehqqvkbqmvlzvmlzmzdzdbvmmmzimmqvleggmzigqmivqzqhvkezgmjvvivvg...

output:

1421341

result:

ok 1 number(s): "1421341"

Test #20:

score: 0
Accepted
time: 9ms
memory: 65336kb

input:

cccfcccffcffffffcfffffccffffffcccffffcffccfcffcfcfffcfcffcfcfcccccccfcffcfccccccffcccfcccfcccccccffcffffffcfccffcccfcfccfcffcfffccffccfffffccfcffcffffffffccfffffffccffcfccfcfcfffccfffffccccfcfccfccfcfcfccccfcccffccccfcccfccccfcfcffcccffcfffcfcccccffccfcccccccfffcffcccccccccccccfcfcffcffcffcffcffcfcf...

output:

3118221

result:

ok 1 number(s): "3118221"

Test #21:

score: 0
Accepted
time: 362ms
memory: 298856kb

input:

srrsrssrrsssrsrsrsrrrrrssrrssrsrsssrrrrsssrrsrrrsrrrrssrsssrssrrrsrrsrsssssrrrrrrrrrrsrrssrsrrrrrsssrrrrsssrsrrsrsssrrrrrsrrssrrssrrrrsrrsrsrsrrrsrrrrssrrssssrsrrrrsrssrsrsssssssrsrrsrrrrrsrssssrrsssrsssrrrrsssssrsrrrsssrssrrrssrsrsssssrrrssrrrrrsssrrsrrsrrrssrrssrsrsrssssrssssrsrrrsrrssrsrsrsrsrsrr...

output:

75529025

result:

ok 1 number(s): "75529025"

Test #22:

score: 0
Accepted
time: 358ms
memory: 298380kb

input:

onpboooppuaeabbabzpoopnqpopnyrabrrpbyorlebzprboypaprrpabebdobozuborppyualtbzauprrobnrqbzuzrrbebotqulratlrobaoyztyrpqqroorbyledaropnnploroabtelydozdopabapqubynynubpybptpoopnyrolparqpaoooobbperyuezponoboyuaopbpqpporplbdrooozbybueyrpnpzodrroyarzbpzyprpdpzboaaobpppalllranutyaobbdptrpprzubdbryapbudylbqab...

output:

3326939

result:

ok 1 number(s): "3326939"

Test #23:

score: 0
Accepted
time: 3ms
memory: 64140kb

input:

etweelwwwwwtttweetleettetlwwlltwwettwtwwlttletlwtltwtwelltetteleelelwwttelwleweltewtwllltwweeelwtweweeweetltttwtelteltwtewteetwwtltwetlteettelwtewtlletlltllwtweewletwtwtleewttlellwwteettlwtttwteetwwltwttelltweetttwtelleleetwewlewewewtewtetttweteeweltltelwwlwltlletwlweelelwlwelelettwllwlewleteeteellw...

output:

547040

result:

ok 1 number(s): "547040"

Test #24:

score: 0
Accepted
time: 7ms
memory: 65328kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

38791844792

result:

ok 1 number(s): "38791844792"

Test #25:

score: 0
Accepted
time: 119ms
memory: 167408kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

4804791846049

result:

ok 1 number(s): "4804791846049"

Test #26:

score: 0
Accepted
time: 384ms
memory: 299268kb

input:

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

10043476749324

result:

ok 1 number(s): "10043476749324"

Test #27:

score: 0
Accepted
time: 330ms
memory: 244976kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269398620

result:

ok 1 number(s): "269398620"

Test #28:

score: 0
Accepted
time: 322ms
memory: 249664kb

input:

yhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyhyyhyhhyyhhyhyyhyhhyhyyhhyyhyhhyyhhyhyyhhyyh...

output:

269769773

result:

ok 1 number(s): "269769773"

Test #29:

score: 0
Accepted
time: 335ms
memory: 248288kb

input:

baababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabba...

output:

287077563

result:

ok 1 number(s): "287077563"

Extra Test:

score: 0
Extra Test Passed