답안 #1116007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116007	2024-11-21T07:39:48 Z	vjudge1	CSS (COI14_css)	C++17	100 / 100	431 ms	79432 KB

#include <cstdio>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <unordered_map>
using namespace std;
struct E
{
    int v, t;
} e[100050];
unordered_map<string, bool> C[10050];
int n, m, k, c, o, h[10050], f[10050];
bool Z[5050], X[5050][5050], Y[5050][5050];
string _, a[10050];
vector<string> Q, w[10050];
void A(int u, int v) { e[++c] = {v, h[u]}, h[u] = c; }
void D(int u)
{
    for (int i = h[u], v; i; i = e[i].t)
    {
        X[v = e[i].v][0] = 1;
        Y[v][0] = 1;
        for (int j = 1; j <= k; ++j)
        {
            if (Z[j])
                X[v][j] = X[u][j - 1];
            else
                X[v][j] = Y[u][j - 1];
            if (X[v][j])
            {
                for (auto _ : w[j])
                    X[v][j] &= C[v].count(_);
            }
            Y[v][j] = Y[u][j] || X[v][j];
        }
        D(v);
    }
}
int main()
{
    cin >> n;
    getline(cin, _);
    for (int i = 0, u = 0; i < n; ++i)
    {
        getline(cin, _);
        if (_.back() == '\r')
            _.pop_back();
        if (_[1] == 'd')
        {
            A(u, ++o), f[o] = u, u = o;
            int x = _.find('\''), y = _.find('\'', x + 1);
            a[u] = _.substr(x + 1, y - x - 1);
            x = _.find('\'', y + 1), y = _.find('\'', x + 1);
            string t = _.substr(x + 1, y - x - 1) + ' ';
            int p = 0;
            while (p < t.size())
            {
                int e = t.find(' ', p);
                C[u][t.substr(p, e - p)] = 1;
                p = e + 1;
            }
        }
        else
            u = f[u];
    }
    cin >> m;
    getline(cin, _);
    for (int i = 0; i < m; ++i)
    {
        getline(cin, _);
        if (_.back() == '\r')
            _.pop_back();
        _ += ' ';
        int p = 0;
        while (p < _.size())
        {
            int e = _.find(' ', p);
            string t = _.substr(p, e - p);
            if (t != ">")
            {
                Z[++k] = 0, t += '.';
                int p = 1;
                while (p < t.size())
                {
                    int e = t.find('.', p);
                    w[k].push_back(t.substr(p, e - p));
                    p = e + 1;
                }
            }
            else
            {
                Z[++k] = 1, p = e + 1, e = _.find(' ', p);
                t = _.substr(p, e - p) + '.';
                int p = 1;
                while (p < t.size())
                {
                    int e = t.find('.', p);
                    w[k].push_back(t.substr(p, e - p));
                    p = e + 1;
                }
            }
            p = e + 1;
        }
        for (int i = 0; i <= k; ++i)
            X[0][i] = Y[0][i] = 0;
        X[0][0] = Y[0][0] = 1;
        D(0);
        for (int i = 0; i <= o; ++i)
            if (X[i][k])
                Q.push_back(a[i]);
        cout << Q.size() << ' ';
        for (auto i : Q)
            cout << i << ' ';
        cout << '\n';
        Q.clear();
        for (int i = 1; i <= k; ++i)
            Z[i] = 0, w[i].clear();
        for (int i = 0; i <= o; ++i)
            for (int j = 0; j <= k; ++j)
                X[i][j] = Y[i][j] = 0;
        k = 0;
    }
    return 0;
}

Compilation message

css.cpp: In function 'int main()':
css.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             while (p < t.size())
      |                    ~~^~~~~~~~~~
css.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while (p < _.size())
      |                ~~^~~~~~~~~~
css.cpp:84:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 while (p < t.size())
      |                        ~~^~~~~~~~~~
css.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 while (p < t.size())
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10832 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	53328 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	414 ms	54476 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	143 ms	79432 KB	Output is correct
2	Correct	262 ms	53576 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	154 ms	77384 KB	Output is correct
2	Correct	256 ms	53776 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10832 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	177 ms	77384 KB	Output is correct
2	Correct	405 ms	54088 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	225 ms	71496 KB	Output is correct
2	Correct	274 ms	52808 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	192 ms	76360 KB	Output is correct
2	Correct	431 ms	54088 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	359 ms	79292 KB	Output is correct
2	Correct	249 ms	53576 KB	Output is correct