QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724028#8031. Gitignoreucup-team3890#AC ✓9ms52352kbC++141.5kb2024-11-08 08:26:272024-11-08 08:26:28

Judging History

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

  • [2024-11-08 08:26:28]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:52352kb
  • [2024-11-08 08:26:27]
  • 提交

answer

#include <iostream>
#include <vector>
#include <map>

int n, m;
std::vector<std::string> s[107], t[107];
std::map<int, int> to[1000007];
int nodecnt, val[1000007];
int newNode() {
  ++nodecnt;
  val[nodecnt] = 0;
  std::map<int, int>().swap(to[nodecnt]);
  return nodecnt;
}
void insert(std::vector<std::string> s, int dd) {
  int p = 1;
  val[p] += dd;
  for (auto i : s) {
    int r = std::hash<std::string>()(i);
    if (to[p].find(r) == to[p].end()) {
      to[p][r] = newNode();
    }
    p = to[p][r];
    val[p] += dd;
  }
}
int dfs(int u) {
  int ans = 0;
  for (auto [r, v] : to[u]) {
    if (val[v] == 0) {
      ++ans;
    } else {
      ans += dfs(v);
    }
  }
  return ans;
}

void solve() {
  nodecnt = 0, newNode();
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    s[i].clear();
    std::string p, q;
    std::cin >> p, p += '/';
    for (char j : p) {
      if (j == '/') {
        s[i].push_back(q), q = "";
      } else {
        q += j;
      }
    }
    insert(s[i], 0);
  }
  for (int i = 1; i <= m; ++i) {
    t[i].clear();
    std::string p, q;
    std::cin >> p, p += '/';
    for (char j : p) {
      if (j == '/') {
        t[i].push_back(q), q = "";
      } else {
        q += j;
      }
    }
    insert(t[i], 1);
  }
  std::cout << dfs(1) << '\n';
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 52276kb

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: 3ms
memory: 50792kb

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: 0ms
memory: 50704kb

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: 4ms
memory: 51960kb

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: 7ms
memory: 52352kb

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: 4ms
memory: 52148kb

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: 7ms
memory: 51316kb

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: 4ms
memory: 50804kb

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: 9ms
memory: 50644kb

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: 6ms
memory: 51176kb

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: 7ms
memory: 50808kb

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: 6ms
memory: 51144kb

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: 0ms
memory: 50520kb

input:

1
0 1
gwqcgbynpocrpypskgqopltsddslexflhojrahekkhwcizptheegbsgjuhzbtebuspaqcouakvnjlcpgvseevrbfidoeeiivotklqmqivyxywdymkwtetgmofpmacjnlrmfrdpbphqfalqkckvfwqeyfjyvyxhaypwtttohlkwtvfhwsryweipzsjgcmkabajvcbmvmnmgtjqbnsbegorhbbdduyydwgvdqsiknyqyymmyfbhlblqktwlzddkaogxportoqxwekgmqhnrniqxnbbhuerexdanjoxat...

output:

0

result:

ok 1 number(s): "0"

Test #14:

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

input:

1
1 0
qyolgljtoqfihnlqwihoebgrybnsflqhphbqxacmfbjyxpklduifmpezuibymuqdrnwjrtcoaybfammtgjbvrlgftoqthiqfzzhnruslyniyfrdojztgvsssqewfpruwamxakcxgyvxcgllzzexlnllpbvkjomnqzgrkbbebzfqtnvdzlxizhxwhrxtilsrskvqogawqasysngiwbgdjnemehdvyycuxrrzescnfheocaeafukcuytgrlshonbnselesermpcatcaqadnndyhpolussxlrdkwzcwdm...

output:

1

result:

ok 1 number(s): "1"

Test #15:

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

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: 7ms
memory: 50992kb

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