QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#545746#8031. Gitignorewzxtsl#ML 1ms4240kbC++173.0kb2024-09-03 16:52:422024-09-03 16:52:44

Judging History

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

  • [2024-09-03 16:52:44]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:4240kb
  • [2024-09-03 16:52:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
const int mod = 998244353;
const int N=2e4+7;
int n,m;
int mm=0;
map<string,int>ac;
int sw(string s){
    mm++;
    ac[s]=mm;
    return mm;
}
struct st{
    int u;
    int v;
    st(int _v):v(_v){}
};
vector<st>e[55];
int mp[N];
int mp1[N];
int cc[N];
int a[N];
void add_s(int s1,int s2){
    if(!mp[s1*10+s2])
    e[s1].push_back((s2)),mp[s1*10+s2]=1;
}
int cnt;
int dfs(int beg){
    int sum=0; //<<beg<<" "<<sum<<endl; 
    for(int j=0;j<e[beg].size();j++){
        if(!mp1[e[beg][j].v]){
            sum++;
            mp1[e[beg][j].v]=1;
            continue;
        }
        else{
            sum+=dfs(e[beg][j].v);
            
        }
    }
  
    return sum;
}
void solve(){
    int ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string str;
        cin>>str;
        string s0;
        int s1;
        int fl=0;
        int len=str.length();
        str+='/';
        for(int j=0;j<=len;j++){
            if(str[j]!='/'){
                s0+=str[j];
            }
            else{
                int ssw;
                if(!ac[s0])
                 ssw=sw(s0);
                 else ssw=ac[s0];
                if(fl==0){
                    s1=ssw;
                    if(!cc[s1])
                    a[cnt++]=s1,cc[s1]=1;
                    fl=1;
                }
                else{
                    add_s(s1,ssw);
                    s1=ssw;
                }
             
                s0.clear();
            }
        }
    }
    for(int i=1;i<=m;i++){
        string str;cin>>str;
        int len=str.length();
        str+='/';
        string s0;
        for(int j=0;j<=len;j++){
            if(str[j]!='/'){
                s0+=str[j];
            }
            else{

                int ssw;
                if(!ac[s0])ssw=sw(s0);
                else ssw=ac[s0];
            
                mp1[ssw]=1;
                s0.clear();
            }
        }
    }
  //  for(int i=0;i<cnt;i++)cout<<a[i]<<" "; 
    for(int i=0;i<cnt;i++){
        if(!mp1[a[i]]){
            ans++;
            mp1[a[i]]=1;
         //   cout<<a[i]<<"!"<<endl;
        }
        else{
            ans+=dfs(a[i]);
            //cout<<"!"<<a[i]<<endl;
        }
        
        
    }
    cout<<ans<<endl;
}

signed main(){
    fast;
    int t=1;
    cin>>t;
    while(t--){
        mm=0;
        memset(e,0,sizeof(e));
        memset(mp,0,sizeof(mp));
        memset(mp1,0,sizeof(mp1));
        memset(a,0,sizeof(a));
        memset(cc,0,sizeof(cc));
        ac.clear();
        cnt=0;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 4160kb

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

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:


result: