Submission #727446

#	Time	Username	Problem	Language	Result	Execution time	Memory
727446		finn__	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	98 ms	19216 KiB

watchmen

#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<tuple<unsigned, unsigned, unsigned>,
                   vector<tuple<unsigned, unsigned, unsigned>>,
                   greater<tuple<unsigned, unsigned, unsigned>>>
        q;
    q.emplace(0, 0, 0);
    t[0][0] = 0;
    while (!q.empty())
    {
        auto [d, u, s] = q.top();
        q.pop();
        if (d != t[u][s])
            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, 0);
                    }
                }
                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 + 1) % l[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, (x + 1) % l[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, 0);
                    }
                    ++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] &&
                            (c[u] != c[w] || resid[u] != ((resid[w] + 1) % l[u]) || (d % 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 + 1) % l[w]);
                        }
                        if (c[w] != c[u] && x + 1 < t[w][(x + 1) % l[w]])
                        {
                            t[w][(x + 1) % l[w]] = x + 1;
                            q.emplace(x + 1, w, (x + 1) % l[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] &&
                            (c[u] != c[w] || resid[u] != (resid[w] + 1) % l[u] || d % 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 + 1) % l[w]);
                        }
                        d += l[u];
                        if ((d + 1) % l[w] != resid[w] &&
                            (c[u] != c[w] || resid[u] != (resid[w] + 1) % l[u] || d % 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 + 1) % l[w]);
                        }
                        x = d + (resid[w] - d % l[w] + l[w]) % l[w];
                        if (x % l[u] != resid[u] && c[w] != c[u] && x + 1 < t[w][(x + 1) % l[w]])
                        {
                            t[w][(x + 1) % l[w]] = x + 1;
                            q.emplace(x + 1, w, (x + 1) % l[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, (d + 1) % l[u]);
            }
        }
    }

    cout << "impossible\n";
}

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