QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763466#8031. Gitignorewifi32767AC ✓28ms155532kbC++202.2kb2024-11-19 20:25:482024-11-19 20:25:50

Judging History

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

  • [2024-11-19 20:25:50]
  • 评测
  • 测评结果:AC
  • 用时:28ms
  • 内存:155532kb
  • [2024-11-19 20:25:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = uint64_t;
// #define int ll
#define endl '\n'
const int MAX = 5e5 + 5, mod = 1e9 + 7;

hash<string> hs;
struct TRIE{
    static const int M = 3e6 + 10, N = 65;
    int size = 0;
    vector<map<ull, int>> tree;
    vector<int> status;
    TRIE(){
        tree.resize(M);
        status.resize(M);
    }
    void clear(){
        for (int i = 0; i <= size; i ++){
            tree[i].clear();
            status[i] = 0;
        }
        size = 0;
    }
    void insert(const vector<ull> &a, int st){
        int cur = 0;
        for (int i = 0; i < a.size(); i ++){
            if (tree[cur].find(a[i]) == tree[cur].end()){
                tree[cur][a[i]] = ++size;
            }
            cur = tree[cur][a[i]];
            status[cur] |= st;
        }
    }
    int dfs(int cur){
        int ans = 0;
        if (status[cur] == 1) return 1;
        if (status[cur] == 2) return 0;
        for (auto [u, v] : tree[cur]){
            ans += dfs(v);
        }
        // cerr << cur << ' ' << ans << endl;
        return ans;
    }
};
TRIE trie;
void solve(){
    int n, m;
    cin >> n >> m;
    trie.clear();
    for (int i = 0; i < n; i ++){
        string s; cin >> s;
        string t;
        vector<ull> a;
        for (int i = 0; i < s.size(); i ++){
            if (s[i] == '/'){
                a.push_back(hs(t));
                t.clear();
            }
            else{
                t += s[i];
            }
        }
        a.push_back(hs(t));
        trie.insert(a, 1);
    }
    for (int i = 0; i < m; i ++){
        string s; cin >> s;
        string t;
        vector<ull> a;
        for (int i = 0; i < s.size(); i ++){
            if (s[i] == '/'){
                a.push_back(hs(t));
                t.clear();
            }
            else{
                t += s[i];
            }
        }
        a.push_back(hs(t));
        trie.insert(a, 2);
    }
    cout << trie.dfs(0) << endl;
    // cerr << endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;cin>>T;while(T--)
    solve();
}

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

详细

Test #1:

score: 100
Accepted
time: 19ms
memory: 155500kb

input:

2
3 0
data/train
data/test
model
3 1
data/train
data/test
model
data/sample

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: 0
Accepted
time: 28ms
memory: 155340kb

input:

5
0 10
szhps/mb/yz
szhps/mb/fb/rf/auw
szhps/or/ui
hy/xkd/k
szhps/mb/fb/rf/mu
cf/rnd/wjv/xdda
szhps/izh
gi
szhps/mb/fb/xwe
hy/xkd/jbq
0 20
gjy/imp/mxuvi/z/ao
gjy/s/zft/jxzm
gjy/ob/mwvf/la
gjy/imp/supe/oxne/p
gjy/ob/mwvf/eums/agfb
gjy/imp/mxuvi/z/anaj
gjy/ob/mwvf/eums/tv
gjy/ob/mwvf/eums/x/gg
gjy/s/ak...

output:

0
0
0
0
0

result:

ok 5 number(s): "0 0 0 0 0"

Test #3:

score: 0
Accepted
time: 16ms
memory: 155404kb

input:

6
0 14
evs
r/gvzgs/pbs/b/riip
r/gvzgs/brps
r/gvzgs/pbs/nj
r/gvzgs/bl/rhyx/var
hg/tdcl
r/gvzgs/pbs/fbs/rle
r/gvzgs/pt/ncvnc/le/zzpy
r/gvzgs/pbs/fbs/xf
wux/ts/jxc
bo/olh
mx/yuw
r/gvzgs/pt/ncvnc/le/gxv
bo/axyv
2 11
nt/tulqv
m/i/i
n
noqdi/lt
m/cim
noqdi/jnz
m/i/k
m/otb
m/i/gd
nt/ndxv
nt/x/hta
noqdi/rxbb...

output:

0
2
0
1
2
1

result:

ok 6 numbers

Test #4:

score: 0
Accepted
time: 28ms
memory: 155532kb

input:

5
6 10
j/yems/b/oqr/jl
usm/pa/wv
j/gj/uq
j/epdo/u
j/epdo/r
j/yems/fg
j/epdo/nbck
usm/nnbr/pik
usm/pa/nqf
j/e
usm/pa/kub
j/epdo/vvk/eno/zs/mtz
j/epdo/vvk/jvf
j/epdo/vvk/eno/rdgm
usm/pa/zp
j/epdo/fe/qc
3 9
qn/wiy/wneh
qn/wiy/uc
f/yp
dpb/dq
dpb/fv
dpb/fyvn
dpb/s/iias/ddu/fnx
jp/nu
dpb/s/odpn/nloco
f/kt...

output:

5
3
5
5
3

result:

ok 5 number(s): "5 3 5 5 3"

Test #5:

score: 0
Accepted
time: 20ms
memory: 155516kb

input:

5
5 7
v/uhh
v/sh/oc
v/sh/ah/emn
v/qisc/lrs/fu/hir
v/sh/ah/xtkr
v/sh/xa
v/qisc/lrs/fu/je
v/qisc/snm
qq
v/sh/ah/mlf/uw
v/qisc/iu
v/y/lj/cui
3 12
za
qojw/n
qojw/lzf/c/sk
qojw/lzf/f/vo
yr/m
qojw/lzf/f/jov/ii
qojw/o/c
cdzz/ytsg
ptcc
qojw/o/xu/yd
qojw/fk
cdzz/wos/ul
yr/pxw/pe
cdzz/pp/luyl
qojw/o/kvk
8 7
d...

output:

5
3
7
2
4

result:

ok 5 number(s): "5 3 7 2 4"

Test #6:

score: 0
Accepted
time: 19ms
memory: 155504kb

input:

5
2 12
yt/t/d
ksbj/ng/dt/uy/fkxj
ksbj/ng/dt/mu
ksbj/yp/ycqx/wab
yt/t/wi/aznd/yhw
wcx/ruyf/xl
yt/t/fb/xlo
wcx/ckg/lo/zdy
yt/u/oe
wcx/ckg/b/izg/p
ksbj/ng/dt/uy/o
yt/t/m
wcx/ruyf/cw
wcx/ckg/lo/v/o
10 11
fjj/hh
fjj/ssmj/ps/oqw
jl/tuk
fjj/jx/t/vz
jl/rqu/uxf/ep/gw/vsw
jl/rqu/uxf/yxa/hgi
jl/rqu/uxf/aj
jl/r...

output:

2
9
7
6
4

result:

ok 5 number(s): "2 9 7 6 4"

Test #7:

score: 0
Accepted
time: 27ms
memory: 155292kb

input:

6
6 9
gb/gbbf/zfc
gb/u/wi/lt
gb/nu/gr/qmm
gb/u/qk
gb/nryf
gb/a
gb/nu/wgk/pam
yic/hxk
gb/u/jbn
yic/fh
i/ega
gb/mb
yic/iqud
gb/af/n
yic/sfdkr
8 5
fxkx/ocp/k/v
ennb/yvds/tu/qp
fxkx/yf/vej/fyi/pn
fxkx/ocp/ools/l
u/kzfr/s/ra
fxkx/ocp/v
u/zziyn/c
u/zziyn/xh
ennb/zb
u/kzfr/s/vxa
fxkx/ocp/ools/ey/sj
ennb/qk...

output:

6
7
7
9
8
8

result:

ok 6 numbers

Test #8:

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

input:

5
7 5
bwb/bi/ypkg
zqty/xmoe
bvj/k/op
bvj/c
eoi/vlg
ru/gtqpn/kgr/u
ru/gtqpn/qt
bvj/yr/gphz/jza
bvj/yzly
bvj/yr/gphz/seu/ngdk
ngz/zuo
ru/gtqpn/kgr/kl
12 3
h/rn/r/qw
h/rn/yh
h/ci/j/bix/o/ifn/izx
hw/hzpm/oiha
h/ci/j/fbd
hw/z
h/b
h/a/aglgu/o/w
h/ci/j/qk/vgg/sd
h/a/qcfl
h/a/fzv
h/rn/rfb
sb
h/ci/j/qk/mf
hw...

output:

7
8
8
11
5

result:

ok 5 number(s): "7 8 8 11 5"

Test #9:

score: 0
Accepted
time: 23ms
memory: 155240kb

input:

5
15 5
ci/htmlv/pi/c/xx/oq/jg
ci/xenm/cyb
ci/htmlv/pi/i
ci/xenm/g/izso
ci/xenm/g/kyh
ci/htmlv/pi/si/mg
dbwy/fla
ci/ae/yogs/tl
dbwy/qqzkc
ci/xenm/to
ci/ae/zva
dpzj/v
xsq
ci/htmlv/pi/jm
ci/htmlv/ucz
pz
ci/ae/cmj
ci/htmlv/hy/uf
ci/htmlv/pi/c/xx/g/dzj/tr
ci/xenm/cfmwj/z
9 4
grnh/tvy/ulv
grnh/tvy/tppt
b/...

output:

13
7
6
5
9

result:

ok 5 number(s): "13 7 6 5 9"

Test #10:

score: 0
Accepted
time: 15ms
memory: 155240kb

input:

6
10 5
dv/vbrw/ywjl/exqm/ncb/kl
mjoon/x
dv/fuuv/pcpx
dv/fuuv/k
okrvn/be/iv
mjoon/hn/xca/b/lghn
dv/vbrw/ywjl/exqm/ncb/zng
dv/vbrw/ywjl/exqm/zyt/db
hxa/esz
dv/fuuv/at
dv/ivs
dv/rjde
dv/vbrw/eqk
mjoon/hn/n
hxa/mllb
9 2
gwv/lil/mvid/xni/rnn
gwv/pdu/sp/ad/jn
gwv/pdu/sp/ad/ailw/lbf
gwv/lxjya
gwv/pdu/sp/ad...

output:

6
3
10
6
4
9

result:

ok 6 numbers

Test #11:

score: 0
Accepted
time: 15ms
memory: 155320kb

input:

5
10 0
g/zhix/bby/l
g/zhix/wj/vx/kyf/yx/kh
ch/ifyp
g/zhix/wj/irng
g/zhix/v
g/zhix/wj/vx/kyf/ui
g/zhix/wj/vx/kyf/tuc
g/zhix/wj/vx/kyf/yx/h/nzdh
g/zhix/wj/vx/kyf/yx/sw/jer
de/peol
12 3
yrmci/vho/qwdml/qr
zfa
yrmci/vho/aqx/tsv
yrmci/vho/aa/ia/jic/ni/w
yrmci/vho/aa/ia/wj/yg
yrmci/vho/aa/ys/cyc/ugr/fj
yr...

output:

3
9
13
10
8

result:

ok 5 number(s): "3 9 13 10 8"

Test #12:

score: 0
Accepted
time: 15ms
memory: 155240kb

input:

6
14 0
ya/wqx/df
sec/gl/ccqyx
ya/wqx/xm/bjqso/qafm/lv
sec/wo/bmbv
ya/wqx/xm/bjqso/qafm/xjlz
sec/nap/p/kee/tk
sec/wo/hzjvl
ya/wqx/xm/njp
sec/nap/t
sec/gl/guqi
sec/r
sec/gl/a
ya/wqx/xm/bjqso/w
ejbnm/enk/aa
14 0
jt/y/artnh/m
xk
gum/hgyl
gum/gvm/bqk
gum/lchu/rt/wdh/ur
gum/id/wxu
jt/y/cu
jt/lfkl/mxj
jt/y...

output:

3
3
3
7
3
5

result:

ok 6 numbers

Test #13:

score: 0
Accepted
time: 15ms
memory: 155324kb

input:

1
0 1
gwqcgbynpocrpypskgqopltsddslexflhojrahekkhwcizptheegbsgjuhzbtebuspaqcouakvnjlcpgvseevrbfidoeeiivotklqmqivyxywdymkwtetgmofpmacjnlrmfrdpbphqfalqkckvfwqeyfjyvyxhaypwtttohlkwtvfhwsryweipzsjgcmkabajvcbmvmnmgtjqbnsbegorhbbdduyydwgvdqsiknyqyymmyfbhlblqktwlzddkaogxportoqxwekgmqhnrniqxnbbhuerexdanjoxat...

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 24ms
memory: 155452kb

input:

1
1 0
qyolgljtoqfihnlqwihoebgrybnsflqhphbqxacmfbjyxpklduifmpezuibymuqdrnwjrtcoaybfammtgjbvrlgftoqthiqfzzhnruslyniyfrdojztgvsssqewfpruwamxakcxgyvxcgllzzexlnllpbvkjomnqzgrkbbebzfqtnvdzlxizhxwhrxtilsrskvqogawqasysngiwbgdjnemehdvyycuxrrzescnfheocaeafukcuytgrlshonbnselesermpcatcaqadnndyhpolussxlrdkwzcwdm...

output:

1

result:

ok 1 number(s): "1"

Test #15:

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

input:

1
38 40
b/y/r/s/s/u/a/n/y
b/y/g/f/c
a/n/b/k/z
b/y/r/e/x/l/o
b/y/g/y/p/r/r/k/q/q/x
b/y/r/e/w/c
b/y/g/a/t/l
a/b
u/m/i
c/p/b
a/z/x/l
b/y/g/y/p/r/r/k/q/q/v
b/y/r/e/x/x
b/y/r/s/s/u/p
b/y/r/s/s/u/a/n/o/t/p/c
b/y/g/f/o
b/y/g/y/p/k/b/w/o
b/y/g/y/p/k/b/x/o
a/n/b/k/s
b/y/r/s/s/y/i
b/y/t/s
b/y/r/s/h/f
a/n/d/c/...

output:

34

result:

ok 1 number(s): "34"

Test #16:

score: 0
Accepted
time: 16ms
memory: 155480kb

input:

3
2 0
abc/de
ab/cde
2 1
ab/cde
ab/c/de
ab/c/d/e
2 1
ab/c/de
ab/cde
ab/c/d/e

output:

2
2
2

result:

ok 3 number(s): "2 2 2"

Extra Test:

score: 0
Extra Test Passed