Submission #985560

#	Time	Username	Problem	Language	Result	Execution time	Memory
985560		maomao90	Board Game (JOI24_boardgame)	C++17	100 / 100	2487 ms	93900 KiB

Main

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <bitset>
#include <map>
#include <queue>
#include <cassert>
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<ll, ll, ll> lll;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 50005;
const int BLK = 300;
//const int MAXN = 50;
//const int BLK = 1;

int n, m, k;
vi adj[MAXN];
string s;
int x[MAXN];

namespace SmallKSolver {
    ll base[MAXN], delta[MAXN];
    int rawd[MAXN], goodd[MAXN];
    ll d[2][MAXN];
    queue<int> qu;
    deque<int> dq;
    priority_queue<lll, vector<lll>, greater<lll>> pq;
    bool fix[MAXN];
    ll ans[MAXN];
    int main() {
        // distance to closest stop
        REP (i, 0, n) {
            rawd[i] = INF;
        }
        REP (i, 0, n) {
            if (s[i] == '1') {
                qu.push(i);
                rawd[i] = 0;
            }
        }
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for (int v : adj[u]) {
                if (mnto(rawd[v], rawd[u] + 1)) {
                    qu.push(v);
                }
            }
        }
        REP (i, 0, n) {
            if (rawd[i] == 0) {
                rawd[i] = 2;
            }
        }
        REP (i, 1, k) {
            base[0] += rawd[x[i]];
        }
        // "good" vertex is stop cell and has adjacent stop cell
        // distance to closest "good" vertex
        REP (i, 0, n) {
            goodd[i] = INF;
        }
        REP (i, 0, n) {
            if (s[i] == '0') {
                continue;
            }
            bool gd = 0;
            for (int v : adj[i]) {
                if (s[v] == '1') {
                    gd = 1;
                    break;
                }
            }
            if (gd) {
                goodd[i] = 0;
                dq.push_back(i);
            }
        }
        while (!dq.empty()) {
            int u = dq.front(); dq.pop_front();
            for (int v : adj[u]) {
                if (mnto(goodd[v], goodd[u] + (s[u] == '0'))) {
                    if (s[u] == '0') {
                        dq.push_back(v);
                    } else {
                        dq.push_front(v);
                    }
                }
            }
        }
        REP (i, 1, k) {
            delta[i - 1] = goodd[x[i]] - rawd[x[i]];
        }
        sort(delta, delta + k - 1);
        cerr << base[0] << '\n';
        REP (i, 1, k) {
            base[i] = base[i - 1] + delta[i - 1];
            cerr << i << ": " << delta[i - 1] << ' ' << base[i] << '\n';
        }
        // get answer without stop cells
        REP (i, 0, n) {
            ans[i] = LINF;
        }
        ans[x[0]] = 0;
        qu.push(x[0]);
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for (int v : adj[u]) {
                if (mnto(ans[v], ans[u] + 1) && s[v] == '0') {
                    qu.push(v);
                }
            }
        }
        REP (i, 0, n) {
            fix[i] = ans[i] != LINF;
        }
        REP (g, 0, k) {
            cerr << g << '\n';
            REP (i, 0, n) {
                d[0][i] = d[1][i] = LINF;
            }
            d[0][x[0]] = 0;
            pq.push({0, x[0], 0});
            while (!pq.empty()) {
                auto [ud, u, t] = pq.top(); pq.pop();
                if (d[t][u] != ud) {
                    continue;
                }
                for (int v : adj[u]) {
                    bool b = u != x[0] && s[u] == '1';
                    if (mnto(d[b | t][v], ud + (b ? 2 * k - 1 - g : 1))) {
                        pq.push({d[b | t][v], v, b | t});
                    }
                }
            }
            REP (i, 0, n) {
                mnto(ans[i], d[1][i] + base[g] - 2 * (k - 1 - g));
                cerr << ' ' << i << ": " << d[i] << ' ' << ans[i] << '\n';
            }
        }
        REP (i, 0, n) {
            cout << ans[i] << '\n';
        }
        return 0;
    }
}

namespace BigKSolver {
    ll delta[MAXN], cost[MAXN];
    int rawd[MAXN], goodd[MAXN];
    queue<int> qu;
    deque<int> dq;
    priority_queue<lll, vector<lll>, greater<lll>> pq;
    int mnl[MAXN];
    ll d[MAXN][MAXN / BLK + 50];
    ll ans[MAXN];
    int main() {
        int MAXL = n / (k - 1) + 10;
        // distance to closest stop
        REP (i, 0, n) {
            rawd[i] = INF;
        }
        REP (i, 0, n) {
            if (s[i] == '1') {
                qu.push(i);
                rawd[i] = 0;
            }
        }
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for (int v : adj[u]) {
                if (mnto(rawd[v], rawd[u] + 1)) {
                    qu.push(v);
                }
            }
        }
        // "good" vertex is stop cell and has adjacent stop cell
        // distance to closest "good" vertex
        REP (i, 0, n) {
            goodd[i] = INF;
        }
        REP (i, 0, n) {
            if (s[i] == '0') {
                continue;
            }
            bool gd = 0;
            for (int v : adj[i]) {
                if (s[v] == '1') {
                    gd = 1;
                    break;
                }
            }
            if (gd) {
                goodd[i] = 0;
                dq.push_back(i);
            }
        }
        while (!dq.empty()) {
            int u = dq.front(); dq.pop_front();
            for (int v : adj[u]) {
                if (mnto(goodd[v], goodd[u] + (s[v] == '0'))) {
                    if (s[v] == '0') {
                        dq.push_back(v);
                    } else {
                        dq.push_front(v);
                    }
                }
            }
        }
        REP (i, 0, n) {
            goodd[i] += s[i] == '1';
        }
        REP (i, 0, n) {
            if (rawd[i] == 0) {
                rawd[i] = min(goodd[i], 2);
            }
        }
        ll base = 0;
        REP (i, 1, k) {
            base += rawd[x[i]];
        }
        REP (i, 1, k) {
            delta[i - 1] = goodd[x[i]] - rawd[x[i]];
            cerr << delta[i - 1] << "\n";
        }
        sort(delta, delta + k - 1);
        cost[1] = base;
        int ptr = 0;
        REP (i, 2, n + 1) {
            while (ptr < k - 1 && delta[ptr] <= i - 2) {
                ptr++;
            }
            cost[i] = cost[i - 1] + 2 * (k - 1) - ptr;
            cerr << i << ": " << cost[i] << "\n";
        }

        REP (i, 0, n) {
            mnl[i] = INF;
        }
        mnl[x[0]] = 0;
        dq.pb(x[0]);
        while (!dq.empty()) {
            int u = dq.front(); dq.pop_front();
            for (int v : adj[u]) {
                bool b = u != x[0] && s[u] == '1';
                if (mnto(mnl[v], mnl[u] + b)) {
                    if (b) {
                        dq.push_back(v);
                    } else {
                        dq.push_front(v);
                    }
                }
            }
        }

        REP (i, 0, n) {
            ans[i] = LINF;
            REP (j, 0, MAXL) {
                d[i][j] = LINF;
            }
        }
        d[x[0]][0] = 0;
        pq.push({0, x[0], 0});
        while (!pq.empty()) {
            auto [ud, u, l] = pq.top(); pq.pop();
            if (ud != d[u][l - mnl[u]]) {
                continue;
            }
            for (int v : adj[u]) {
                bool b = u != x[0] && s[u] == '1';
                if (l + b - mnl[v] < MAXL && mnto(d[v][l + b - mnl[v]], ud + 1)) {
                    pq.push({d[v][l + b - mnl[v]], v, l + b});
                }
            }
        }

        REP (i, 0, n) {
            REP (j, 0, min(MAXL, n - mnl[i] + 1)) {
                mnto(ans[i], d[i][j] + cost[j + mnl[i]]);
            }
        }

        REP (i, 0, n) {
            cout << ans[i] << '\n';
        }
        return 0;
    }
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> m >> k;
    REP (i, 0, m) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin >> s;
    REP (i, 0, k) {
        cin >> x[i];
        x[i]--;
    }
    if (k <= BLK) {
        return SmallKSolver::main();
    } else {
        return BigKSolver::main();
    }
}

• 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