Submission #1318295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318295		LIA	Board Game (JOI24_boardgame)	C++17	100 / 100	1456 ms	7044 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
#define pll pair<ll, ll>

const ll inf = 1e18;
ll n, m, k;
v<v<ll>> g;
string str;
v<ll> type, dist1, dist2, c, csum, ans, dist;
v<bool> chk;

struct state {
    ll idx, cnt, val, jump;
    bool operator<(const state &b) const {
        return val - csum[cnt] > b.val - csum[b.cnt];
    }
};

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

    cin >> n >> m >> k;
    g.resize(n + 1);
    type.resize(n + 2, 0);
    dist1.resize(n + 2, inf);
    dist2.resize(n + 2, inf);
    c.resize(n + 2, 0);
    csum.resize(n + 2, 0);
    ans.resize(n + 2, inf);
    dist.resize(n + 2, inf);
    chk.resize(n + 2, false);

    lp(i, 0, m) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    ll s;
    cin >> str >> s;
    str = "0" + str;

    lp(i, 1, n + 1) {
        if (str[i] == '1') {
            bool f = false;
            for (ll nx : g[i]) f |= (str[nx] == '1');
            type[i] = f ? 2 : 1;
        }
    }

    queue<tuple<ll, ll, ll>> qq;
    lp(i, 1, n + 1) {
        if (type[i] == 1) {
            chk[i] = true;
            qq.push({i, i, 0});
        }
    }
    while (!qq.empty()) {
        auto [idx, frm, val] = qq.front();
        qq.pop();
        dist1[idx] = val;
        for (ll nx : g[idx]) {
            if (!chk[nx]) {
                chk[nx] = true;
                qq.push({nx, frm, val + 1});
            }
        }
    }

    deque<ll> dq;
    lp(i, 1, n + 1) {
        if (type[i] == 2) {
            dq.push_back(i);
            dist2[i] = 0;
        }
    }
    while (!dq.empty()) {
        ll cur = dq.front();
        dq.pop_front();
        for (ll nx : g[cur]) {
            if (type[cur] != 1) {
                if (dist2[nx] > dist2[cur] + 1) {
                    dist2[nx] = dist2[cur] + 1;
                    dq.push_back(nx);
                }
            } else {
                if (dist2[nx] > dist2[cur]) {
                    dist2[nx] = dist2[cur];
                    dq.push_front(nx);
                }
            }
        }
    }

    lp(i, 0, k - 1) {
        ll x;
        cin >> x;

        if (dist2[x] >= inf) {
            if (!type[x]) {
                c[1] += dist1[x];
                c[2] += -dist1[x] + 2;
            } else {
                c[1] += 2;
            }
        } else if (dist1[x] >= inf) {
            if (!type[x]) {
                c[1] += dist2[x];
                c[2] += -dist2[x] + 1;
            } else {
                c[1] += 1;
            }
        } else if (!type[x]) {
            if (dist1[x] >= dist2[x]) {
                c[1] += dist2[x];
                c[2] += -dist2[x] + 1;
            } else {
                c[1] += dist1[x];
                c[2] += -dist1[x] + 2;
                c[min(n + 1, 2 + dist2[x] - dist1[x])] -= 1;
            }
        } else if (type[x] == 1) {
            c[1] += 2;
            c[dist2[x]] -= 1;
        } else {
            c[1] += 1;
        }
    }

    ll add = 0;
    lp(i, 1, n + 1) {
        add += c[i];
        c[i] = add;
        csum[i] = csum[i - 1] + c[i];
        ans[i] = inf;
        dist[i] = inf;
    }

    priority_queue<state> pq;
    pq.push({s, 0, 0, 0});
    dist[s] = 0;

    while (!pq.empty()) {
        auto [idx, cnt, val, jump] = pq.top();
        pq.pop();

        if (cnt > n) continue;
        ans[idx] = min(ans[idx], val);

        if (jump) {
            if (dist[idx] < inf && val > dist[idx]) continue;
            pq.push({idx, cnt, val + c[cnt], 0});
            continue;
        }

        for (ll nx : g[idx]) {
            if (dist[nx] < inf && val + 1 >= dist[nx]) continue;
            dist[nx] = min(dist[nx], val + 1);
            if (type[nx]) pq.push({nx, cnt + 1, val + 1, 1});
            else pq.push({nx, cnt, val + 1, 0});
        }
    }

    lp(i, 1, n + 1) cout << ans[i] << '\n';

    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 9 / 9
• Subtask 7: 23 / 23
• Subtask 8: 9 / 9