제출 #727453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727453		finn__	From Hacks to Snitches (BOI21_watchmen)	C++17	15 / 100	6035 ms	66176 KiB

watchmen

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 250000;

vector<unsigned> g[N], t[N];
unsigned l[N], resid[N], c[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m;
    cin >> n >> m;
    for (size_t i = 0; i < m; ++i)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }
    size_t k;
    cin >> k;
    for (size_t i = 0; i < k; ++i)
    {
        size_t L;
        cin >> L;
        for (size_t j = 0; j < L; ++j)
        {
            unsigned u;
            cin >> u;
            l[u - 1] = L;
            resid[u - 1] = j;
            t[u - 1].resize(L);
            c[u - 1] = i;
        }
    }

    for (size_t i = 0; i < n; ++i)
    {
        if (t[i].empty())
            t[i].resize(1);
        fill(t[i].begin(), t[i].end(), UINT_MAX);
    }

    priority_queue<pair<unsigned, unsigned>, vector<pair<unsigned, unsigned>>,
                   greater<pair<unsigned, unsigned>>>
        q;
    q.emplace(0, 0);
    t[0][0] = 0;
    while (!q.empty())
    {
        auto [d, u] = q.top();
        q.pop();
        if (d != t[u][l[u] ? d % l[u] : 0])
            continue;
        if (u == n - 1)
        {
            cout << d << '\n';
            return 0;
        }

        if (!l[u])
        {
            for (unsigned const &w : g[u])
                if (!l[w])
                {
                    if (d + 1 < t[w][0])
                    {
                        t[w][0] = d + 1;
                        q.emplace(d + 1, w);
                    }
                }
                else
                {
                    if ((d + 1) % l[w] != resid[w] && d + 1 < t[w][(d + 1) % l[w]])
                    {
                        t[w][(d + 1) % l[w]] = d + 1;
                        q.emplace(d + 1, w);
                    }
                    unsigned const x = d + (resid[w] - (d % l[w]) + l[w]) % l[w];
                    if (x + 1 < t[w][(x + 1) % l[w]])
                    {
                        t[w][(x + 1) % l[w]] = x + 1;
                        q.emplace(x + 1, w);
                    }
                }
        }
        else
        {
            for (auto it = g[u].begin(); it != g[u].end();)
            {
                unsigned &w = *it;
                if (!l[w])
                {
                    if (d + 1 < t[w][0])
                    {
                        t[w][0] = d + 1;
                        q.emplace(d + 1, w);
                    }
                    ++it;
                }
                else
                {
                    if (c[u] == c[w])
                    {
                        if ((d + 1) % l[u] != resid[w] &&
                            (resid[u] != (resid[w] + 1) % l[u] || (d % l[u]) != resid[w]) &&
                            d + 1 < t[w][(d + 1) % l[u]])
                        {
                            t[w][(d + 1) % l[u]] = d + 1;
                            q.emplace(d + 1, w);
                        }
                        ++it;
                    }
                    else
                    {
                        unsigned x = d + (resid[w] - d % l[w] + l[w]) % l[w];
                        if (x % l[u] != resid[u])
                        {
                            if ((d + 1) % l[w] != resid[w] && d + 1 < t[w][(d + 1) % l[w]])
                            {
                                t[w][(d + 1) % l[w]] = d + 1;
                                q.emplace(d + 1, w);
                            }
                            if (x + 1 < t[w][(x + 1) % l[w]])
                            {
                                t[w][(x + 1) % l[w]] = x + 1;
                                q.emplace(x + 1, w);
                            }
                            size_t i = it - g[u].begin();
                            swap(w, g[u].back());
                            g[u].pop_back();
                            it = g[u].begin() + i;
                        }
                        else
                        {
                            if ((d + 1) % l[w] != resid[w] && d + 1 < t[w][(d + 1) % l[w]])
                            {
                                t[w][(d + 1) % l[w]] = d + 1;
                                q.emplace(d + 1, w);
                            }
                            d += l[u];
                            if ((d + 1) % l[w] != resid[w] &&
                                d + 1 < t[w][(d + 1) % l[w]])
                            {
                                t[w][(d + 1) % l[w]] = d + 1;
                                q.emplace(d + 1, w);
                            }
                            x = d + (resid[w] - d % l[w] + l[w]) % l[w];
                            if (x % l[u] != resid[u] && x + 1 < t[w][(x + 1) % l[w]])
                            {
                                t[w][(x + 1) % l[w]] = x + 1;
                                q.emplace(x + 1, w);
                            }
                            ++it;
                        }
                    }
                }
            }
            if ((d + 1) % l[u] != resid[u] && d + 1 < t[u][(d + 1) % l[u]])
            {
                t[u][(d + 1) % l[u]] = d + 1;
                q.emplace(d + 1, u);
            }
        }
    }

    cout << "impossible\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20