QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395657#7076. Browser Gamessuibian_xiaozhao#ML 0ms0kbC++231.4kb2024-04-21 17:02:152024-04-21 17:02:15

Judging History

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

  • [2024-04-21 17:02:15]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-04-21 17:02:15]
  • 提交

answer

//
// Created by DELLPC on 24-4-21.
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 5;

string s[maxn];

int en(char c) {
    if (c == '/')
        return 0;
    if (c == '.')
        return 1;
    return c - 'a' + 2;
}

map<int, int> nex[maxn * 50];
int cn[maxn * 50], ab[maxn * 50], f[maxn * 50];
int cnt = 1;

void insert(string ss) {
    int p = 1;
    int n = ss.size();
    vector<int> v;
    for (int i = 0; i < n; i++) {
        if (!nex[p][en(ss[i])])
            nex[p][en(ss[i])] = ++cnt;
        p = nex[p][en(ss[i])];
        v.push_back(p);
        cn[p]++;
    }
}

int sol(string ss) {
    vector<int> v;
    int p = 1;
    int n = ss.size();
    v.push_back(1);
    for (int i = 0; i < n; i++) {
        p = nex[p][en(ss[i])];
        cn[p]--;
        ab[p]++;
        f[p] = 0;
        v.push_back(p);
    }
    for(int i = n; i >= 1; i--) {
        p = v[i];
        for (auto [_, x]: nex[p]) {
            f[p] += f[x];
        }
        if (cn[p] == 0) {
            f[p] = 1;
        }
    }

    f[1] = 0;
    for(auto [_, x]:nex[1]) {
        f[1] += f[x];
    }
    return f[1];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        insert(s[i]);
    }
    for (int i = 0; i < n; i++) {
        cout << sol(s[i]) << endl;
    }
    return 0;
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

3
ufoipv.ofu
hsbocmvfgboubtz.kq
hfotijo.njipzp.dpn/kb

output:

1
2
2

result: