QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645155#8031. Gitignoregjlccc#WA 6ms25880kbC++171.6kb2024-10-16 17:05:092024-10-16 17:05:09

Judging History

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

  • [2024-10-16 17:05:09]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:25880kb
  • [2024-10-16 17:05:09]
  • 提交

answer

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
#define pb push_back
#define endl "\n"
using namespace std;

const int N = 2e5 + 10;

int n, m;
int c0, c1;
set<int> h[N];
map<string, int> ids[N];

int w[N], dp[N][4];
void dfs(int u) {
  dp[u][0] = 0, dp[u][1] = 1, dp[u][2] = 0, dp[u][3] = 1;
  if (!h[u].size()) {
    if (!w[u]) {
      dp[u][0] = 1e9, dp[u][1] = 1;
      dp[u][2] = 0, dp[u][3] = 2;
    } else {
      dp[u][0] = 0, dp[u][1] = 2;
      dp[u][2] = 1e9, dp[u][3] = 1;
    }
  }
  for (auto j : h[u]) {
    dfs(j);
    dp[u][0] += min(dp[j][0], dp[j][1]);
    dp[u][1] += min(dp[j][2], dp[j][1] - 1);
    dp[u][2] += min(dp[j][2], dp[j][3]);
    dp[u][3] += min(dp[j][3] - 1, dp[j][0]);
  }
}
void solve() {
  cin >> c0 >> c1;

  int idx = 1;
  ids[1].clear(), h[1].clear(), w[1] = 0;
  _for(i, 1, c0 + c1) {
    string s;
    cin >> s;
    int rt = 1;
    for (int l = 0, r = 0; l < s.size(); l = r + 1, r = l) {
      while (r < s.size() && s[r] != '/') r++;
      string t = s.substr(l, r - l);
      if (!ids[rt].count(t)) {
        ids[rt][t] = ++idx;
        h[rt].insert(idx);
        h[idx].clear();
        ids[idx].clear();
        w[idx] = 0;
      }
      rt = ids[rt][t];
    }
    w[rt] = i > c0;
  }
  dfs(1);
  cout << dp[1][0] << endl;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
}
/*

2
3 0
d/t
d/tt
m
3 1
d/t
d/tt
m
d/s

1
3 0
d/t
d/tt
m
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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: -100
Wrong Answer
time: 3ms
memory: 24604kb

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:

5
6
7
8
7
8

result:

wrong answer 1st numbers differ - expected: '6', found: '5'