oj.uz

Submission #727452

# Submission time Handle Problem Language Result Execution time Memory
727452 2023-04-20T17:31:02 Z finn__ From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 104748 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13040 KB Output is correct
2 Correct 71 ms 19156 KB Output is correct
3 Correct 70 ms 19720 KB Output is correct
4 Correct 99 ms 19988 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 71 ms 19916 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12932 KB Output is correct
2 Correct 71 ms 19180 KB Output is correct
3 Correct 66 ms 19732 KB Output is correct
4 Correct 102 ms 19980 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 75 ms 19704 KB Output is correct
7 Correct 79 ms 19820 KB Output is correct
8 Correct 75 ms 19788 KB Output is correct
9 Correct 77 ms 19748 KB Output is correct
10 Correct 81 ms 19932 KB Output is correct
11 Correct 67 ms 19776 KB Output is correct
12 Correct 71 ms 19816 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12932 KB Output is correct
2 Correct 71 ms 19180 KB Output is correct
3 Correct 66 ms 19732 KB Output is correct
4 Correct 102 ms 19980 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 75 ms 19704 KB Output is correct
7 Correct 79 ms 19820 KB Output is correct
8 Correct 75 ms 19788 KB Output is correct
9 Correct 77 ms 19748 KB Output is correct
10 Correct 81 ms 19932 KB Output is correct
11 Correct 67 ms 19776 KB Output is correct
12 Correct 71 ms 19816 KB Output is correct
13 Correct 18 ms 13624 KB Output is correct
14 Correct 73 ms 20220 KB Output is correct
15 Correct 68 ms 19716 KB Output is correct
16 Correct 97 ms 19924 KB Output is correct
17 Correct 8 ms 12076 KB Output is correct
18 Correct 69 ms 19788 KB Output is correct
19 Correct 65 ms 19804 KB Output is correct
20 Correct 70 ms 19916 KB Output is correct
21 Correct 71 ms 19780 KB Output is correct
22 Correct 78 ms 19928 KB Output is correct
23 Correct 66 ms 19816 KB Output is correct
24 Correct 67 ms 19692 KB Output is correct
25 Correct 1490 ms 99964 KB Output is correct
26 Correct 1476 ms 104744 KB Output is correct
27 Correct 1232 ms 100532 KB Output is correct
28 Correct 1081 ms 104748 KB Output is correct
29 Execution timed out 6078 ms 95416 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12932 KB Output is correct
2 Correct 71 ms 19180 KB Output is correct
3 Correct 66 ms 19732 KB Output is correct
4 Correct 102 ms 19980 KB Output is correct
5 Correct 8 ms 12076 KB Output is correct
6 Correct 75 ms 19704 KB Output is correct
7 Correct 79 ms 19820 KB Output is correct
8 Correct 75 ms 19788 KB Output is correct
9 Correct 77 ms 19748 KB Output is correct
10 Correct 81 ms 19932 KB Output is correct
11 Correct 67 ms 19776 KB Output is correct
12 Correct 71 ms 19816 KB Output is correct
13 Correct 18 ms 13624 KB Output is correct
14 Correct 73 ms 20220 KB Output is correct
15 Correct 68 ms 19716 KB Output is correct
16 Correct 97 ms 19924 KB Output is correct
17 Correct 8 ms 12076 KB Output is correct
18 Correct 69 ms 19788 KB Output is correct
19 Correct 65 ms 19804 KB Output is correct
20 Correct 70 ms 19916 KB Output is correct
21 Correct 71 ms 19780 KB Output is correct
22 Correct 78 ms 19928 KB Output is correct
23 Correct 66 ms 19816 KB Output is correct
24 Correct 67 ms 19692 KB Output is correct
25 Correct 1490 ms 99964 KB Output is correct
26 Correct 1476 ms 104744 KB Output is correct
27 Correct 1232 ms 100532 KB Output is correct
28 Correct 1081 ms 104748 KB Output is correct
29 Execution timed out 6078 ms 95416 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13040 KB Output is correct
2 Correct 71 ms 19156 KB Output is correct
3 Correct 70 ms 19720 KB Output is correct
4 Correct 99 ms 19988 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 71 ms 19916 KB Output is correct
7 Correct 18 ms 12932 KB Output is correct
8 Correct 71 ms 19180 KB Output is correct
9 Correct 66 ms 19732 KB Output is correct
10 Correct 102 ms 19980 KB Output is correct
11 Correct 8 ms 12076 KB Output is correct
12 Correct 75 ms 19704 KB Output is correct
13 Correct 79 ms 19820 KB Output is correct
14 Correct 75 ms 19788 KB Output is correct
15 Correct 77 ms 19748 KB Output is correct
16 Correct 81 ms 19932 KB Output is correct
17 Correct 67 ms 19776 KB Output is correct
18 Correct 71 ms 19816 KB Output is correct
19 Correct 7 ms 12080 KB Output is correct
20 Correct 6 ms 12040 KB Output is correct
21 Correct 6 ms 12072 KB Output is correct
22 Correct 20 ms 13624 KB Output is correct
23 Correct 73 ms 20288 KB Output is correct
24 Correct 91 ms 19728 KB Output is correct
25 Correct 92 ms 19908 KB Output is correct
26 Correct 7 ms 12080 KB Output is correct
27 Correct 77 ms 19780 KB Output is correct
28 Correct 67 ms 19788 KB Output is correct
29 Correct 71 ms 19724 KB Output is correct
30 Correct 66 ms 19800 KB Output is correct
31 Correct 70 ms 19884 KB Output is correct
32 Correct 65 ms 19764 KB Output is correct
33 Correct 74 ms 19792 KB Output is correct
34 Incorrect 1434 ms 100172 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13040 KB Output is correct
2 Correct 71 ms 19156 KB Output is correct
3 Correct 70 ms 19720 KB Output is correct
4 Correct 99 ms 19988 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 71 ms 19916 KB Output is correct
7 Correct 18 ms 12932 KB Output is correct
8 Correct 71 ms 19180 KB Output is correct
9 Correct 66 ms 19732 KB Output is correct
10 Correct 102 ms 19980 KB Output is correct
11 Correct 8 ms 12076 KB Output is correct
12 Correct 75 ms 19704 KB Output is correct
13 Correct 79 ms 19820 KB Output is correct
14 Correct 75 ms 19788 KB Output is correct
15 Correct 77 ms 19748 KB Output is correct
16 Correct 81 ms 19932 KB Output is correct
17 Correct 67 ms 19776 KB Output is correct
18 Correct 71 ms 19816 KB Output is correct
19 Correct 18 ms 13624 KB Output is correct
20 Correct 73 ms 20220 KB Output is correct
21 Correct 68 ms 19716 KB Output is correct
22 Correct 97 ms 19924 KB Output is correct
23 Correct 8 ms 12076 KB Output is correct
24 Correct 69 ms 19788 KB Output is correct
25 Correct 65 ms 19804 KB Output is correct
26 Correct 70 ms 19916 KB Output is correct
27 Correct 71 ms 19780 KB Output is correct
28 Correct 78 ms 19928 KB Output is correct
29 Correct 66 ms 19816 KB Output is correct
30 Correct 67 ms 19692 KB Output is correct
31 Correct 1490 ms 99964 KB Output is correct
32 Correct 1476 ms 104744 KB Output is correct
33 Correct 1232 ms 100532 KB Output is correct
34 Correct 1081 ms 104748 KB Output is correct
35 Execution timed out 6078 ms 95416 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13040 KB Output is correct
2 Correct 71 ms 19156 KB Output is correct
3 Correct 70 ms 19720 KB Output is correct
4 Correct 99 ms 19988 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 71 ms 19916 KB Output is correct
7 Correct 18 ms 12932 KB Output is correct
8 Correct 71 ms 19180 KB Output is correct
9 Correct 66 ms 19732 KB Output is correct
10 Correct 102 ms 19980 KB Output is correct
11 Correct 8 ms 12076 KB Output is correct
12 Correct 75 ms 19704 KB Output is correct
13 Correct 79 ms 19820 KB Output is correct
14 Correct 75 ms 19788 KB Output is correct
15 Correct 77 ms 19748 KB Output is correct
16 Correct 81 ms 19932 KB Output is correct
17 Correct 67 ms 19776 KB Output is correct
18 Correct 71 ms 19816 KB Output is correct
19 Correct 18 ms 13624 KB Output is correct
20 Correct 73 ms 20220 KB Output is correct
21 Correct 68 ms 19716 KB Output is correct
22 Correct 97 ms 19924 KB Output is correct
23 Correct 8 ms 12076 KB Output is correct
24 Correct 69 ms 19788 KB Output is correct
25 Correct 65 ms 19804 KB Output is correct
26 Correct 70 ms 19916 KB Output is correct
27 Correct 71 ms 19780 KB Output is correct
28 Correct 78 ms 19928 KB Output is correct
29 Correct 66 ms 19816 KB Output is correct
30 Correct 67 ms 19692 KB Output is correct
31 Correct 1490 ms 99964 KB Output is correct
32 Correct 1476 ms 104744 KB Output is correct
33 Correct 1232 ms 100532 KB Output is correct
34 Correct 1081 ms 104748 KB Output is correct
35 Execution timed out 6078 ms 95416 KB Time limit exceeded
36 Halted 0 ms 0 KB -