QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644982#9466. DomainsAfterlife#AC ✓191ms186948kbC++204.5kb2024-10-16 16:19:132024-10-16 16:19:14

Judging History

This is the latest submission verdict.

  • [2024-10-16 16:19:14]
  • Judged
  • Verdict: AC
  • Time: 191ms
  • Memory: 186948kb
  • [2024-10-16 16:19:13]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int n , q;
bool is_domain(char c) {
    return c == '-' || c == '*' || c == '#' || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9') || c == '.' ;
}
bool is_alpha(char c) {
    return 'a' <= c && c <= 'z';
}
bool is_vpn(char c) {
    return c == '-' || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9');
}
int to_int(char c) {
    if('a' <= c && c <= 'z') return c- 'a';
    if('0' <= c && c <= '9') return c - '0' + 26 ;
    if(c == '-') return 36;
    if(c == '*') return 37;
    if(c == '#') return 38;
    if(c == '.') return 39;
    assert(0);
}
const int N = 2e6 + 5;
struct trie {
    int ch[40];
    int cnt[3]; //// *count , #count , blankcount
    int cur[3];
}T[N];
int rt , cc;
void cls(int u) {
    memset(T[u].cnt , 0 , sizeof(T[u].cnt)) ;
    memset(T[u].cur , 0 , sizeof(T[u].cur));
    memset(T[u].ch,0,sizeof(T[u]));
}
bool ins(string s) {
    int u = rt;
    reverse(s.begin() , s.end());
    int tc ;
    if(s.back() == '*') tc = 0 , s.pop_back();
    else if(s.back() == '#') tc = 1 , s.pop_back();
    else tc = 2;

    for(int i = 0;i < s.size();i++) {
        int t = to_int(s[i]) ;
        if(!T[u].ch[t]) {
            T[u].ch[t] = ++cc;
            cls(cc);
        }
        if(T[u].cur[0]) return 0;
        if(tc == 1 && T[u].cur[1]) return 0;
        u = T[u].ch[t];
    }
    if(T[u].cur[0]) return 0;
    if(tc == 1 && T[u].cur[1]) return 0;

    if(tc == 0) {
        if(T[u].cnt[0] || T[u].cnt[1] || T[u].cnt[2]) return 0;
    }
    else if(tc == 1) {
        if(T[u].cnt[1]) return 0;
    }
    else {
        if(T[u].cur[2]) return 0;
    }
    
    u = rt;
    for(int i = 0;i < s.size();i++) {
        int t = to_int(s[i]) ;
        T[u].cnt[tc]++ ;
        u = T[u].ch[t];
    }
    T[u].cnt[tc]++ ;T[u].cur[tc]++ ;
    // printf("Ad %d %d\n",u,tc);
    return 1;
}
int calc(string t) {
    reverse(t.begin() , t.end()) ;
    int tc;
    if(t.back() == '*') tc = 0 , t.pop_back() ;
    else tc = 2;

    int ans = 0 , ans1 = 0;
    int u = rt;
    for(int i = 0;i < t.size();i++) {
        ans += T[u].cur[0] ;
        ans1 += T[u].cur[1] ;
        // printf("tu %d : %d\n",u,T[u].cur[0]);
        if(T[u].cur[0]) ans1 = 0;
        int tt = to_int(t[i]) ;

        if(T[u].ch[tt] == 0) {
            u = cc + 1 ;
            cls(cc + 1) ;
            break ;
        }
        u = T[u].ch[tt];
    }
    ans += T[u].cur[0];
    ans1 += T[u].cur[1] ;
    if(T[u].cur[0]) ans1 = 0;

    if(tc == 2) {
        ans += T[u].cur[2] ;
        // printf("Tcur %d : %d\n",T[u].cur[0] , u);
        if(ans) return ans;
        return ans1;
    }
    else {
        ans += (T[u].cnt[0] - T[u].cur[0]) ;
        ans += T[u].cnt[2] ;
        ans1 += (T[u].cnt[1] - T[u].cur[1]) ;
        return ans + ans1;
    }
    // if(ans ) return ans;
    // return ans1;
}
void solv() {
    int cnt = 0; rt = 0;cc = 0;
    cls(0);
    for(int i = 1;i <= n;i++) {
        string a,b;cin >> a >> b;
        bool ff = 1;
        for(auto x : a) {
            if(!is_domain(x)) {ff = 0 ;break ;}
        }
        if(a[0] == '.' || a.back() == '.') ff =0;
        for(int i = 0;i + 1 < a.size();i++) {
            if(a[i] == '.' && a[i + 1] == '.') ff = 0;
        }
        if((a[0] == '#' || a[0] == '*') && (a.size() > 1 && a[1] != '.')) ff = 0;
        for(int i = 1;i < a.size();i++) {
            if(a[i] == '#' || a[i] == '*') ff = 0;
        }
        for(int i = 0;i < a.size();i++) {
            if(a[i] == '-') {
                if(i == 0 || i == a.size() - 1) ff = 0;
                else if(!is_alpha(a[i - 1]) || !is_alpha(a[i + 1])) ff = 0;
            }
        }

        for(auto x : b) {
            if(!is_vpn(x)) ff = 0;
        }
        if(!is_alpha(b[0])) ff = 0;
        for(int i = 0;i < b.size();i++) {
            if(b[i] == '-') {
                if(i == 0 || i == b.size() - 1) ff = 0;
                else if(!is_alpha(b[i - 1]) || !is_alpha(b[i + 1])) ff = 0;
            }
        }
        if(!ff) {
            // cout << "bad1 " << i << '\n';
            ++cnt ; continue ;
        }
        if(!ins(a)) {
            // cout << "bad2 " << i << '\n';
            ++cnt ; continue ;
        }
    }
    cout << cnt << '\n' ;
    cin >> q;
    while(q--) {
        string t ; cin >> t;
        cout << calc(t) << '\n';

    }
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    while(cin >> n) solv() ;
    return 0;
}

詳細信息

Test #1:

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

input:

11
a.c a.c
poj.org vpn-china
www.pku.edu.cn vpn-pku1
mail.pku.edu.cn vpn-pku1
*.test.pku.edu.cn vpn-pku2
*.test.pku.edu.cn vpn-pku2
*.a.test.pku.edu.cn vpn-pku2
*.test2.pku.edu.cn vpn-pku2
*.pku.edu.cn vpn-pku2
#.pku.edu.cn vpn-pku0
#.www.pku.edu.cn vpn-pku0
5
a.c
mail.pku.edu.cn
*.test.pku.edu.cn
*...

output:

5
0
1
1
5
6

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 191ms
memory: 186948kb

input:

1
nwlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmcoqhnwnkuewhsqmgbbuqcljjivswmdkqtbxixmvtrrbljptnsnfwzqfjmafadrrwsofsbcnuvqhffbsaqxwpqcacehchzvfrkmlnozjkpqpxrjxkitzyxacbhhkicqcoendtomfgdwdwfcgpxiqvkuytdlcgdewhtaciohordtqkvwcsgspqoqmsboaguwnnyqxnzlgdgwpbtrwblnsadeu...

output:

0
0
20883
51
1
1
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
0
1
1
1
0
1
0
0
0
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
4
1
0
0
1
1
1
1
1
0
1
0
0
1
0
1
0
1
1
0
0
0
0
1
1
1
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
0
1
0
0
0
0
0
0
1
1
1
0
1
0
1
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
1...

result:

ok 156302 lines