QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#656494 | #8031. Gitignore | yumingsk# | WA | 1ms | 5592kb | C++20 | 2.8kb | 2024-10-19 13:12:31 | 2024-10-19 13:12:31 |
Judging History
answer
#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";
using namespace std;
const int Mod = 998244353;
using ll = long long;
int dp[100005];
struct node
{
int id;
string s;
node(string s, int id)
{
this->s = s;
this->id = id;
}
};
int tot = 0;
vector<node> e[100005];
void insert(string str, int fa, int opt)
{
int pos = 0;
string cur = "";
while (pos < str.size())
{
cur = "";
// cout << "?" << pos << '\n';
while (pos < str.size() && str[pos] != '/')
{
cur += str[pos];
// cout << str[pos] << '\n';
pos++;
}
if (str[pos] == '/')
pos++;
if (pos > str.size())
break;
// cout << pos << ' ' << cur << '\n';
int fh = 0;
for (auto v : e[fa])
{
if (v.s == cur)
{
fa = v.id;
fh = 1;
break;
}
}
if (fh == 0)
{
e[fa].push_back(node(cur, ++tot));
fa = tot;
}
if (opt == 1 && pos == str.size())
{
dp[tot] = 1;
}
}
}
void dfs(int u, int fa)
{
for (auto v : e[u])
{
if (v.id == fa)
continue;
// cout << v.s << ' ' << v.id << ' ' << dp[v.id] << " " << fa << '\n';
dfs(v.id, u);
dp[u] |= dp[v.id];
}
}
int ans = 0;
void work(int u, int fa)
{
for (auto v : e[u])
{
if (v.id == fa)
continue;
if (dp[v.id] == 0)
{
// cout << v.id << ' ' << v.s << '\n';
ans++;
}
else
{
work(v.id, u);
}
}
}
void solve()
{
int n, m;
ans = 0;
dp[0] = 1;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
insert(s, 0, 0);
}
for (int i = 1; i <= m; i++)
{
string s;
cin >> s;
insert(s, 0, 1);
}
dfs(0, 0);
work(0, 0);
cout << ans << '\n';
for (int i = 0; i <= tot; i++)
{
e[i].clear();
}
tot = 0;
}
int main()
{
IOS;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#ifndef ONLINE_JUDGE
clock_t start_time = clock();
#endif
int t = 1;
cin >> t;
while (t--)
{
solve();
}
#ifndef ONLINE_JUDGE
cout << "Used " << (double)(clock() - start_time) << " ms" << endl;
#endif
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3480kb
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: 3596kb
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: -100
Wrong Answer
time: 1ms
memory: 5592kb
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 0 0 0 0 0
result:
wrong answer 2nd numbers differ - expected: '2', found: '0'