QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#781936#8031. GitignoreUnstalian#AC ✓2ms7960kbC++201.4kb2024-11-25 18:05:302024-11-25 18:05:32

Judging History

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

  • [2024-11-25 18:05:32]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:7960kb
  • [2024-11-25 18:05:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define maxn 1000006
int n, m, cnt;
map<string, int> vis;
int can[maxn], cost[maxn];
vector<int> E[1000005];
int get_id(string &s){
	if(vis.count(s)) return vis[s];
	return vis[s] = ++ cnt;
}
void dfs(int u = 1) {
	for (auto v : E[u]) dfs(v), can[u] |= can[v];
	// cout << u<<" "<< cost[u]<<endl;
	if(!can[u]) cost[u] = 1;
	else {
		cost[u] = 0;
		for (auto v : E[u]) {
			cost[u] += cost[v];	
		}
	}
}
void solve(){
	cnt = 1;
	cin >> n>> m;
	for (int i = 1;i <= n;i ++){
		string s, tmp;
		cin >> s;
		s += '/';
		int last = 1;
		for (auto c : s){
			if(c == '/'){
				E[last].push_back(get_id(tmp));
				last = get_id(tmp);
			}
			tmp += c;
		}
	}
	
	for (int i = 1;i <= m;i ++){
		string s, tmp;
		cin >> s;
		s = s + '/';
		int last = 1;
		for (auto c : s){
			if(c == '/'){
				E[last].push_back(get_id(tmp));
				last = get_id(tmp);
			}
			tmp += c;
		}
		can[last] = 1;
	}
	for (int i = 1;i <= cnt;i ++) {
		sort(E[i].begin(), E[i].end());
		E[i].erase(unique(E[i].begin(), E[i].end()), E[i].end());
	}
	dfs(1);
	int ans = 0;
	for (auto v : E[1]) ans += cost[v];
	cout << ans<<endl;
	for (int i = 1;i <= cnt;i ++) {
		E[i].clear();
		can[i] = 0;
		cost[i] = 0;
	}
	vis.clear();
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T;
	while (T --)
		solve();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5708kb

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

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

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

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

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

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

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

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

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

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

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

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

input:

1
0 1
gwqcgbynpocrpypskgqopltsddslexflhojrahekkhwcizptheegbsgjuhzbtebuspaqcouakvnjlcpgvseevrbfidoeeiivotklqmqivyxywdymkwtetgmofpmacjnlrmfrdpbphqfalqkckvfwqeyfjyvyxhaypwtttohlkwtvfhwsryweipzsjgcmkabajvcbmvmnmgtjqbnsbegorhbbdduyydwgvdqsiknyqyymmyfbhlblqktwlzddkaogxportoqxwekgmqhnrniqxnbbhuerexdanjoxat...

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 2ms
memory: 5648kb

input:

1
1 0
qyolgljtoqfihnlqwihoebgrybnsflqhphbqxacmfbjyxpklduifmpezuibymuqdrnwjrtcoaybfammtgjbvrlgftoqthiqfzzhnruslyniyfrdojztgvsssqewfpruwamxakcxgyvxcgllzzexlnllpbvkjomnqzgrkbbebzfqtnvdzlxizhxwhrxtilsrskvqogawqasysngiwbgdjnemehdvyycuxrrzescnfheocaeafukcuytgrlshonbnselesermpcatcaqadnndyhpolussxlrdkwzcwdm...

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 2ms
memory: 7624kb

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

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