QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#395654 | #7076. Browser Games | suibian_xiaozhao# | RE | 12ms | 122568kb | C++23 | 1.4kb | 2024-04-21 17:01:04 | 2024-04-21 17:01:05 |
Judging History
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...