QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#656494#8031. Gitignoreyumingsk#WA 1ms5592kbC++202.8kb2024-10-19 13:12:312024-10-19 13:12:31

Judging History

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

  • [2024-10-19 13:12:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5592kb
  • [2024-10-19 13:12:31]
  • 提交

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'