QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#697238#8031. GitignoredechancerRE 1ms3824kbC++201.5kb2024-11-01 12:18:492024-11-01 12:18:49

Judging History

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

  • [2024-11-01 12:18:49]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3824kb
  • [2024-11-01 12:18:49]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tc;
  cin >> tc;
  while (tc--) {
    int n, m;
    cin >> n >> m;

    map<string, int> idx;
    vector edge(0, tuple(0, 0, 0));

    auto addEdge = [&](string& s, int tag) {
      for (int j = 0, prev = 0; j < s.size(); j++) {
        int e = find(s.begin() + j, s.end(), '/') - s.begin();
        string t = string(s.begin(), s.begin() + e);
        if (idx.contains(t)) {
          prev = idx[t];
          continue;
        } else {
          idx[t] = idx.size() + 1;
          edge.emplace_back(prev, idx[t], tag);
          j = e;
          prev = idx[t];
        }
      }
    };

    for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      addEdge(s, 1);
    }
    for (int i = 0; i < m; i++) {
      string s;
      cin >> s;
      addEdge(s, 0);
    }

    vector adj(idx.size() + 1, vector(0, pair(0, 0)));
    for (auto& [u, v, tag] : edge) {
      adj[u].emplace_back(v, tag);
    }

    int ans = 0;
    vector dp(n, 1);
    auto dfs = [&](auto&& self, int u) -> void {
      for (auto& [v, tag] : adj[u]) {
        self(self, v);
        if (adj[v].size() == 0) {
          dp[v] = tag;
        }
        dp[u] &= dp[v] == true;
      }
      if (dp[u] == false or u == 0) {
        for (auto& [v, tag] : adj[u]) {
          ans += dp[v];
        }
      }
    };
    dfs(dfs, 0);

    cout << ans << '\n';
  }

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: