QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395654#7076. Browser Gamessuibian_xiaozhao#RE 12ms122568kbC++231.4kb2024-04-21 17:01:042024-04-21 17:01:05

Judging History

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

  • [2024-04-21 17:01:05]
  • 评测
  • 测评结果:RE
  • 用时:12ms
  • 内存:122568kb
  • [2024-04-21 17:01:04]
  • 提交

answer

//
// Created by DELLPC on 24-4-21.
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4 + 5;

string s[maxn];

int en(char c) {
    if (c == '/')
        return 0;
    if (c == '.')
        return 1;
    return c - 'a' + 2;
}

map<int, int> nex[maxn * 50];
int cn[maxn], ab[maxn], f[maxn];
int cnt = 1;

void insert(string ss) {
    int p = 1;
    int n = ss.size();
    vector<int> v;
    for (int i = 0; i < n; i++) {
        if (!nex[p][en(ss[i])])
            nex[p][en(ss[i])] = ++cnt;
        p = nex[p][en(ss[i])];
        v.push_back(p);
        cn[p]++;
    }
}

int sol(string ss) {
    vector<int> v;
    int p = 1;
    int n = ss.size();
    v.push_back(1);
    for (int i = 0; i < n; i++) {
        p = nex[p][en(ss[i])];
        cn[p]--;
        ab[p]++;
        f[p] = 0;
        v.push_back(p);
    }
    for(int i = n; i >= 1; i--) {
        p = v[i];
        for (auto [_, x]: nex[p]) {
            f[p] += f[x];
        }
        if (cn[p] == 0) {
            f[p] = 1;
        }
    }

    f[1] = 0;
    for(auto [_, x]:nex[1]) {
        f[1] += f[x];
    }
    return f[1];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        insert(s[i]);
    }
    for (int i = 0; i < n; i++) {
        cout << sol(s[i]) << endl;
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 122384kb

input:

3
ufoipv.ofu
hsbocmvfgboubtz.kq
hfotijo.njipzp.dpn/kb

output:

1
2
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 12ms
memory: 122328kb

input:

3
hfotijo.njipzp.dpn/kb
hsbocmvfgboubtz.kq
ufoipv.ofu

output:

1
1
2

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 12ms
memory: 122276kb

input:

1
a

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 12ms
memory: 122568kb

input:

2
a
b

output:

1
2

result:

ok 2 lines

Test #5:

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

input:

3
a.b/e
a.c/e
a.d/e

output:

1
2
1

result:

ok 3 lines

Test #6:

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

input:

5
wow
war
world
red
glasses

output:

1
2
1
2
3

result:

ok 5 lines

Test #7:

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

input:

28
aa
ab
ac
ad
ae
af
ag
ah
ai
aj
ak
al
am
an
ao
ap
aq
ar
as
at
au
av
aw
ax
ay
az
b
cd

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1
2
3

result:

ok 28 lines

Test #8:

score: -100
Runtime Error

input:

50000
aaab
aaac
aaad
aaae
aaaf
aaag
aaah
aaai
aaaj
aaak
aaal
aaam
aaan
aaao
aaap
aaaq
aaar
aaas
aaat
aaau
aaav
aaaw
aaax
aaay
aaaz
aaba
aabb
aabc
aabd
aabe
aabf
aabg
aabh
aabi
aabj
aabk
aabl
aabm
aabn
aabo
aabp
aabq
aabr
aabs
aabt
aabu
aabv
aabw
aabx
aaby
aabz
aaca
aacb
aacc
aacd
aace
aacf
aacg
aach...

output:


result: