제출 #1276498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276498		cpismylifeOwO	Viruses (BOI20_viruses)	C++20	100 / 100	332 ms	27380 KiB

Viruses

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e2 + 5;

int g, n, m;
vector<int> nxt[MaxN];
vector<int> trans[MaxN];

void Inp()
{
    cin >> g >> n >> m;
    for (int x = 1; x <= n; x++)
    {
        int u, k;
        cin >> u >> k;
        trans[u].push_back(x);
        for (int y = 1; y <= k; y++)
        {
            int p;
            cin >> p;
            nxt[x].push_back(p);
        }
    }
}

struct Node
{
    int child[2];
    int nxt[2];
    int par, cnt, suflink, exist, prech;

    Node() = default;

    Node(int p, int ch)
    {
        par = p;
        prech = ch;
        exist = 0;
        cnt = child[0] = child[1] = nxt[0] = nxt[1] = suflink = -1;
    }
};

int curPos;
Node Trie[MaxN * MaxN];

int GetNxt(int u, int k);

int SufLink(int u)
{
    if (Trie[u].suflink == -1)
    {
        if (u == 0 || Trie[u].par == 0)
        {
            Trie[u].suflink = 0;
        }
        else
        {
            Trie[u].suflink = GetNxt(SufLink(Trie[u].par), Trie[u].prech);
        }

    }
    return Trie[u].suflink;
}

int GetNxt(int u, int k)
{
    if (Trie[u].nxt[k] == -1)
    {
        if (Trie[u].child[k] == -1)
        {
            if (u == 0)
            {
                Trie[u].nxt[k] = 0;
            }
            else
            {
                Trie[u].nxt[k] = GetNxt(SufLink(u), k);
            }
        }
        else
        {
            Trie[u].nxt[k] = Trie[u].child[k];
        }
    }
    return Trie[u].nxt[k];
}

int Count(int u)
{
    if (u == 0)
    {
        Trie[u].cnt = 0;
        return 0;
    }
    if (Trie[u].cnt != -1)
    {
        return Trie[u].cnt;
    }
    Trie[u].cnt = Count(Trie[u].suflink) + Trie[u].exist;
    return Trie[u].cnt;
}

struct PQNode
{
    int u, st, ed;
    long long w;

    PQNode(int _u, int _st, int _ed, long long _w)
    {
        u = _u;
        st = _st;
        ed = _ed;
        w = _w;
    }

    bool operator < (const PQNode& other) const
    {
        return this->w > other.w;
    }
};

vector<pair<int, int>> graph[2 * MaxN];
vector<pair<int, int>> revgraph[2 * MaxN];
long long F[2 * MaxN][MaxN][MaxN];
bool visited[2 * MaxN][MaxN][MaxN];
priority_queue<PQNode> pq;

void Exc()
{
    curPos = 0;
    Trie[curPos] = Node(-1, -1);
    for (int w = 1; w <= m; w++)
    {
        int k, pos = 0;
        cin >> k;
        for (int x = 1; x <= k; x++)
        {
            int p;
            cin >> p;
            if (Trie[pos].child[p] == -1)
            {
                curPos++;
                Trie[curPos] = Node(pos, p);
                Trie[pos].child[p] = curPos;
            }
            pos = Trie[pos].child[p];
        }
        Trie[pos].exist++;
    }
    for (int x = 0; x <= curPos; x++)
    {
        SufLink(x);
        GetNxt(x, 0);
        GetNxt(x, 1);
    }
    for (int x = 0; x <= curPos; x++)
    {
        Count(x);
    }
    int curn = g - 1;
    for (int u = 0; u < g; u++)
    {
        for (int x : trans[u])
        {
            if ((int)nxt[x].size() == 1)
            {
                graph[nxt[x][0]].push_back(make_pair(u, -1));
            }
            else
            {
                int pre = nxt[x][0];
                for (int y = 1; y < (int)nxt[x].size() - 1; y++)
                {
                    curn++;
                    graph[pre].push_back(make_pair(curn, nxt[x][y]));
                    revgraph[nxt[x][y]].push_back(make_pair(curn, pre));
                    pre = curn;
                }
                graph[pre].push_back(make_pair(u, nxt[x].back()));
                revgraph[nxt[x].back()].push_back(make_pair(u, pre));
            }
        }
    }
    for (int x = 0; x <= curPos; x++)
    {
        if (Trie[x].cnt == 0 && Trie[Trie[x].nxt[0]].cnt == 0)
        {
            pq.push(PQNode(0, x, Trie[x].nxt[0], 1));
        }
        if (Trie[x].cnt == 0 && Trie[Trie[x].nxt[1]].cnt == 0)
        {
            pq.push(PQNode(1, x, Trie[x].nxt[1], 1));
        }
    }
    while (!pq.empty())
    {
        PQNode p = pq.top();
        pq.pop();
        if (visited[p.u][p.st][p.ed])
        {
            continue;
        }
        //cout << p.u << " " << p.st << " " << p.ed << " " << p.w << "\n";
        F[p.u][p.st][p.ed] = p.w;
        visited[p.u][p.st][p.ed] = true;
        for (pair<int, int> x : graph[p.u])
        {
            int v = x.first, w = x.second;
            if (w == -1)
            {
                if (!visited[v][p.st][p.ed])
                {
                    pq.push(PQNode(v, p.st, p.ed, p.w));
                }
            }
            else
            {
                for (int y = 0; y <= curPos; y++)
                {
                    if (Trie[y].cnt == 0 && !visited[v][p.st][y] && visited[w][p.ed][y])
                    {
                        pq.push(PQNode(v, p.st, y, p.w + F[w][p.ed][y]));
                    }
                }
            }
        }
        for (pair<int, int> x : revgraph[p.u])
        {
            int v = x.first, w = x.second;
            for (int y = 0; y <= curPos; y++)
            {
                if (Trie[p.st].cnt == 0 && !visited[v][y][p.ed] && visited[w][y][p.st])
                {
                    pq.push(PQNode(v, y, p.ed, p.w + F[w][y][p.st]));
                }
            }
        }
    }
    for (int x = 2; x < g; x++)
    {
        long long res = -1;
        for (int y = 0; y <= curPos; y++)
        {
            if (visited[x][0][y])
            {
                if (res == -1)
                {
                    res = F[x][0][y];
                }
                res = min(res, F[x][0][y]);
            }
        }
        if (res == -1)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO " << res << "\n";
        }
    }
}

int main()
{
    //freopen("VIRUSES.INP", "r", stdin);
    //freopen("VIRUSES.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32
• Subtask 5: 18 / 18