QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309527#8031. GitignoreEbiarat#TL 0ms3644kbC++202.7kb2024-01-20 17:59:182024-01-20 17:59:19

Judging History

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

  • [2024-01-20 17:59:19]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3644kb
  • [2024-01-20 17:59:18]
  • 提交

answer

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
#include <queue>
#include <sstream>
#include <ctime>
#include <iterator>
#include <string.h>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <fstream>
#include <assert.h>
#include <numeric>
#include <complex>
#include <random>
#include <utility>
#define IOS ios_base::sync_with_stdio(0),cin.tie(0), cout.tie(0);
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a) - 1; i>=(b);i--)
#define rep(i,n) FOR(i,0,n)
#define PB push_back
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define VI vector<int>
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define VL vector<long long >
#define FILL(a, value) memset(a, value, sizeof(a))
const int nax = (int)4e5 + 147;
 
using namespace std;
 
const int MOD = (int)1e9 + 7;
const int INF = 1e9 +47 ;
const long long LINF = (long long)1e18 + 4747;
 
typedef long long LL;

map<string,vector<string >> g;
map<string,bool> ignored;
map<string,int > ign_cnt;
map<string,int > sz;
map<string,int > ans;
map<pair<string,string>,bool> edge;
map<string,int> is_vertex;
void dfs(string v)
{
    sz[v] = is_vertex[v];
    ign_cnt[v] = ignored[v];
    for(auto to : g[v])
    {
        dfs(to);
        sz[v]+=sz[to];
        ign_cnt[v]+=ign_cnt[to];
    }
    if(ign_cnt[v] == sz[v] && v!="ROOT")ans[v] = 1;
    else {
        for(auto to : g[v])ans[v]+=ans[to];
        if(ignored[v])ans[v]++;
    }
 }
void solve()
{
    int n,m;
    cin >> n >> m;
    for(int j = 0;j <n + m ;j ++ )
    {
        string s;
        cin >> s;
        string prev = "ROOT";
        int id = 0;
        while(true) {
           string cur = "";
            while(id < s.size() && s[id]!='/'  )
            {
                cur+=s[id];
                id++;
            }
            if(id == s.size())cur+='#';
            if(!edge.contains({prev,cur})){
                g[prev].push_back(cur);
                edge[{prev,cur}] = true;
            }
            
            if(id == s.size())is_vertex[cur] = true;
            if(j < n && id == s.size()){
                ignored[cur] = true;
            }
            prev = cur ;
            id++;
            if(id >=s.size())break;
        }
    }
    dfs("ROOT");
    cout << ans["ROOT"] << '\n';
    g.clear();
    ignored.clear();
    ign_cnt.clear();
    ans.clear();
    edge.clear();
    is_vertex.clear();
    sz.clear();
}
int main() {
    IOS;
    int tt = 1;
     cin >> tt;
    while(tt--)
    {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

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: