QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#763466 | #8031. Gitignore | wifi32767 | AC ✓ | 28ms | 155532kb | C++20 | 2.2kb | 2024-11-19 20:25:48 | 2024-11-19 20:25:50 |
Judging History
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