QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#697240#8031. GitignoredechancerAC ✓1ms3872kbC++201.5kb2024-11-01 12:20:222024-11-01 12:20:23

Judging History

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

  • [2024-11-01 12:20:23]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3872kb
  • [2024-11-01 12:20:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tc;
  cin >> tc;
  while (tc--) {
    int n, m;
    cin >> n >> m;

    map<string, int> idx;
    vector edge(0, tuple(0, 0, 0));

    auto addEdge = [&](string& s, int tag) {
      for (int j = 0, prev = 0; j < s.size(); j++) {
        int e = find(s.begin() + j, s.end(), '/') - s.begin();
        string t = string(s.begin(), s.begin() + e);
        if (idx.contains(t)) {
          prev = idx[t];
          continue;
        } else {
          idx[t] = idx.size() + 1;
          edge.emplace_back(prev, idx[t], tag);
          j = e;
          prev = idx[t];
        }
      }
    };

    for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      addEdge(s, 1);
    }
    for (int i = 0; i < m; i++) {
      string s;
      cin >> s;
      addEdge(s, 0);
    }

    vector adj(idx.size() + 1, vector(0, pair(0, 0)));
    for (auto& [u, v, tag] : edge) {
      adj[u].emplace_back(v, tag);
    }

    int ans = 0;
    vector dp(idx.size() + 1, 1);
    auto dfs = [&](auto&& self, int u) -> void {
      for (auto& [v, tag] : adj[u]) {
        self(self, v);
        if (adj[v].size() == 0) {
          dp[v] = tag;
        }
        dp[u] &= dp[v] == true;
      }
      if (dp[u] == false or u == 0) {
        for (auto& [v, tag] : adj[u]) {
          ans += dp[v];
        }
      }
    };
    dfs(dfs, 0);

    cout << ans << '\n';
  }

  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3516kb

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

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

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

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

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

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

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

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

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

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

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

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: 3620kb

input:

1
0 1
gwqcgbynpocrpypskgqopltsddslexflhojrahekkhwcizptheegbsgjuhzbtebuspaqcouakvnjlcpgvseevrbfidoeeiivotklqmqivyxywdymkwtetgmofpmacjnlrmfrdpbphqfalqkckvfwqeyfjyvyxhaypwtttohlkwtvfhwsryweipzsjgcmkabajvcbmvmnmgtjqbnsbegorhbbdduyydwgvdqsiknyqyymmyfbhlblqktwlzddkaogxportoqxwekgmqhnrniqxnbbhuerexdanjoxat...

output:

0

result:

ok 1 number(s): "0"

Test #14:

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

input:

1
1 0
qyolgljtoqfihnlqwihoebgrybnsflqhphbqxacmfbjyxpklduifmpezuibymuqdrnwjrtcoaybfammtgjbvrlgftoqthiqfzzhnruslyniyfrdojztgvsssqewfpruwamxakcxgyvxcgllzzexlnllpbvkjomnqzgrkbbebzfqtnvdzlxizhxwhrxtilsrskvqogawqasysngiwbgdjnemehdvyycuxrrzescnfheocaeafukcuytgrlshonbnselesermpcatcaqadnndyhpolussxlrdkwzcwdm...

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 1ms
memory: 3808kb

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

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