Submission #1176246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176246		dpsaveslives	From Hacks to Snitches (BOI21_watchmen)	C++20	100 / 100	1768 ms	136296 KiB

watchmen

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 250010
#define M 6000010
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf;
int rint() {
    int ret = 0;
    char c = getchar();

    while (!isdigit(c))
        c = getchar();

    while (isdigit(c))
        ret = ret * 10 + (c - '0'), c = getchar();

    return ret;
}
int n, m, q, to[M], pre[M], nxt[M], st[N], sid[N], len[N], idx[N], bel[N], cnt = 0;
ll dist[M];
bool vis[M];
int I(int x, int y) {
    return sid[x] + y;
}
ll getnxt(ll t, ll x, ll y) {
    if (t % x <= y) {
        return (t / x) * x + y;
    }

    return (t / x + 1) * x + y;
}
void erz(int x, int i) {
    if (pre[i] >= 0) {
        nxt[pre[i]] = nxt[i];
    } else {
        st[x] = nxt[i];
    }

    if (nxt[i] >= 0) {
        pre[nxt[i]] = pre[i];
    }

    return;
}
int main() {
    int i, j, x, y;
    ll t;
    n = rint(), m = rint();

    for (i = 0; i < n; i++) {
        len[i] = 1;
        st[i] = -1;
    }

    for (i = 0; i < m; i++) {
        x = rint() - 1, y = rint() - 1;
        to[cnt] = y, nxt[cnt] = st[x], pre[cnt] = -1;

        if (st[x] >= 0) {
            pre[st[x]] = cnt;
        }

        st[x] = cnt++;
        to[cnt] = x, nxt[cnt] = st[y], pre[cnt] = -1;

        if (st[y] >= 0) {
            pre[st[y]] = cnt;
        }

        st[y] = cnt++;
    }

    q = rint();

    for (i = 1; i <= q; i++) {
        y = rint();

        for (j = 0; j < y; j++) {
            x = rint() - 1;
            bel[x] = i;
            len[x] = y;
            idx[x] = j;
        }
    }

    for (i = 0; i < n; i++) {
        sid[i + 1] = sid[i] + len[i];
    }

    memset(dist, 63, sizeof(dist));
    priority_queue<pair<ll, pair<int, int>>> pq;
    dist[I(0, 0)] = 0;
    pq.push(make_pair(0, make_pair(0, 0)));

    while (!pq.empty()) {
        t = -pq.top().F, x = pq.top().S.F, y = pq.top().S.S;
        pq.pop();

        if (vis[I(x, y)]) {
            continue;
        }

        vis[I(x, y)] = true;

        if ((y + 1) % len[x] != idx[x] && dist[I(x, (y + 1) % len[x])] > t + 1) {
            dist[I(x, (y + 1) % len[x])] = t + 1;
            pq.push(make_pair(-t - 1, make_pair(x, (y + 1) % len[x])));
        }

        for (i = st[x]; i >= 0; i = nxt[i]) {
            int u = to[i];

            if (len[u] == 1) {
                if (dist[I(u, 0)] > t + 1) {
                    dist[I(u, 0)] = t + 1;
                    pq.push(make_pair(-t - 1, make_pair(u, 0)));
                }

                erz(x, i);
                continue;
            }

            if (len[x] == 1) {
                if ((t + 1) % len[u] != idx[u] && dist[I(u, (t + 1) % len[u])] > t + 1) {
                    dist[I(u, (t + 1) % len[u])] = t + 1;
                    pq.push(make_pair(-t - 1, make_pair(u, (t + 1) % len[u])));
                }

                ll v0 = getnxt(t, len[u], idx[u]);

                if ((v0 + 1) % len[u] != idx[u] && dist[I(u, (v0 + 1) % len[u])] > v0 + 1) {
                    dist[I(u, (v0 + 1) % len[u])] = v0 + 1;
                    pq.push(make_pair(-v0 - 1, make_pair(u, (v0 + 1) % len[u])));
                }

                continue;
            }

            if (bel[x] == bel[u] && idx[u] == (idx[x] + 1) % len[x]) {
                if (dist[I(u, (y + 1) % len[x])] > t + 1) {
                    dist[I(u, (y + 1) % len[x])] = t + 1;
                    pq.push(make_pair(-t - 1, make_pair(u, (y + 1) % len[x])));
                }

                continue;
            }

            if (bel[x] == bel[u] && idx[x] == (idx[u] + 1) % len[x]) {
                if (idx[u] != (y + 1) % len[x] && idx[u] != y) {
                    dist[I(u, (y + 1) % len[x])] = t + 1;
                    pq.push(make_pair(-t - 1, make_pair(u, (y + 1) % len[x])));
                }

                continue;
            }

            if ((t + 1) % len[u] != idx[u] && dist[I(u, (t + 1) % len[u])] > t + 1) {
                dist[I(u, (t + 1) % len[u])] = t + 1;
                pq.push(make_pair(-t - 1, make_pair(u, (t + 1) % len[u])));
            }

            ll v0 = getnxt(t + 1, len[u], idx[u]);

            if (v0 % len[x] != idx[x]) {
                if ((v0 + 1) % len[u] != idx[u] && dist[I(u, (v0 + 1) % len[u])] > v0 + 1) {
                    dist[I(u, (v0 + 1) % len[u])] = v0 + 1;
                    pq.push(make_pair(-v0 - 1, make_pair(u, (v0 + 1) % len[u])));
                }

                erz(x, i);
                continue;
            }

            ll v1 = getnxt(v0, len[x], y), v2 = getnxt(v1, len[u], idx[u]);

            if ((v1 + 1) % len[u] != idx[u] && dist[I(u, (v1 + 1) % len[u])] > v1 + 1) {
                dist[I(u, (v1 + 1) % len[u])] = v1 + 1;
                pq.push(make_pair(-v1 - 1, make_pair(u, (v1 + 1) % len[u])));
            }

            if (v2 % len[x] != idx[x]) {
                if ((v2 + 1) % len[u] != idx[u] && dist[I(u, (v2 + 1) % len[u])] > v2 + 1) {
                    dist[I(u, (v2 + 1) % len[u])] = v2 + 1;
                    pq.push(make_pair(-v2 - 1, make_pair(u, (v2 + 1) % len[u])));
                }
            }
        }
    }

    if (dist[I(n - 1, 0)] > LINF) {
        puts("impossible");
    } else {
        printf("%lld\n", dist[I(n - 1, 0)]);
    }

    return 0;
}

Compilation message (stderr)

watchmen.cpp:4:30: warning: '-fwhole-program' is not an option that controls warnings [-Wpragmas]
    4 | #pragma GCC diagnostic error "-fwhole-program"
      |                              ^~~~~~~~~~~~~~~~~
watchmen.cpp:5:30: warning: '-fcse-skip-blocks' is not an option that controls warnings [-Wpragmas]
    5 | #pragma GCC diagnostic error "-fcse-skip-blocks"
      |                              ^~~~~~~~~~~~~~~~~~~
watchmen.cpp:6:30: warning: '-funsafe-loop-optimizations' is not an option that controls warnings [-Wpragmas]
    6 | #pragma GCC diagnostic error "-funsafe-loop-optimizations"
      |                              ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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