QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744194#8031. GitignoreDoubeecatWA 1ms3780kbC++173.1kb2024-11-13 21:07:182024-11-13 21:07:23

Judging History

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

  • [2024-11-13 21:07:23]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3780kb
  • [2024-11-13 21:07:18]
  • 提交

answer

/*
Undo the destiny.
*/
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
const ll mod = 998244353;
const double eps = 1e-10;
const int N = 1e3 + 10;
map <string,int> nod;
int tot,n,m,f[N],ans,g[N];
vector <vector<int> > G;
vector <int> fa,typ;
bool vis[N];

void dfs(int x,int fat) {
    vis[x] = 1;
    bool flag = 0;
    if (typ[x] <= 1) {
        bool flag = 0;
        for (auto y : G[x]) {
            dfs(y,x);
            if (!g[y]) {
                //cout << "x:" << x << " y:" << y << "\n";
                flag = 1;
            }
        }
        if (!flag) {
            g[x] = 1;
            f[x] = 1;
        } else {
            for (auto y : G[x]) {
                f[x] += f[y];
            }
        }
    } else {
        for (auto y : G[x]) {
            dfs(y,x);
            f[x] += f[y];
        }
    }
}
void solve() {
    cin >> n >> m;
    fa.clear();typ.clear();nod.clear();tot = 0;ans = 0;G.clear();
    fa.resize(1000),typ.resize(1000);G.resize(1000);
    for (int i = 1;i <= n;++i) {
        string lst;
        int lt = 0;
        string st;cin >> st;
        int sz = st.size();
        for (int i = 0;i < sz;++i) {
            string now;
            char c = st[i];
            while (c != '/' && c != '\n' && c != EOF && i < sz) {
                //cout << c << " ";
                now += c;
                c = st[++i];
                if (c == '/' || c == '\n' || c == EOF) break;
            }
            if (!nod.count(now)) {
                nod[now] = ++tot;
            }
            fa[nod[now]] = lt;
            lt = nod[now];
        }
        typ[lt] = 1;
    }
    for (int i = 1;i <= m;++i) {
        string lst;
        int lt = 0;
        string st;cin >> st;
        int sz = st.size();
        for (int i = 0;i < sz;++i) {
            string now;
            char c = st[i];
            while (c != '/' && c != '\n' && c != EOF && i < sz) {
                //cout << c << " ";
                now += c;
                c = st[++i];
                if (c == '/' || c == '\n' || c == EOF) break;
            }
            if (!nod.count(now)) {
                nod[now] = ++tot;
            }
            fa[nod[now]] = lt;
            lt = nod[now];
        
        }
        typ[lt] = 2;
    }
    for (int i = 1;i <= tot;++i) {
        if (fa[i]) {
            //cout << i << " " << fa[i] << "\n";
            //G[i].push_back(fa[i]);
            G[fa[i]].push_back(i);
        }
        vis[i] = f[i] = g[i] = 0;
    }
    /*for (auto [x,y] : nod) {
        cout << x << ":s" << y << "\n";
    }*/
    for (int i = 1;i <= tot;++i) {
        if (!vis[i]) {
            dfs(i,0);
            ans += f[i];
        }
    }
    /*for (int i = 1;i <= tot;++i) {
        cout << "f,g:" << f[i] << " " << g[i] << "\n";
    }*/
    cout << ans <<"\n";
}

signed main() {
    int T;cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3780kb

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

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
1
0
0

result:

wrong answer 3rd numbers differ - expected: '0', found: '1'