Submission #1127485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127485		fzyzzz_z	Road Service 2 (JOI24_ho_t5)	C++20	0 / 100	51 ms	74816 KiB

Main

#include <bits/stdc++.h>
using namespace std;  

struct DSU {
    int E[1000001], _top[1000001], _bot[1000001];
    DSU() { for (int i = 0; i < 1000001; ++i) { E[i] = -1; _top[i] = _bot[i] = i; } }
    int get_parent(int x) { return (E[x] < 0 ? x : E[x] = get_parent(E[x])); }
    int top(int x) { return _top[get_parent(x)]; } 
    int bot(int x) { return _bot[get_parent(x)]; }
    bool unite(int x, int y) {
        x = get_parent(x); 
        y = get_parent(y); 
        if (x == y) return false; 
        if (E[x] > E[y]) swap(x, y); 
        E[x] += E[y]; 
        E[y] = x; 
        _top[x] = min(_top[x], _top[y]); 
        _bot[x] = max(_bot[x], _bot[y]); 
        return true; 
    }
    bool same(int x, int y) {
        return get_parent(x) == get_parent(y); 
    }
}; 

int H, W, Q; 
string A[1000001], B[1000001]; 
// int C[1000001]; 
int bad[1000001];
int last[2][1000001]; 
int best[1000001]; 

const int L = 20; 
int jmp[1000001][L][2]; 

int get_id(int x, int y) {
    return x * W + y; 
}


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

    cin >> H >> W >> Q; 
    DSU ds; 
    for (int i = 0; i < H; ++i) {
        cin >> A[i]; 
        for (int j = 0; j < W - 1; ++j) {
            if (A[i][j] == '1') ds.unite(get_id(i, j), get_id(i, j + 1)); 
        }
    }
    for (int i = 0; i < H - 1; ++i) {
        cin >> B[i]; 
        for (int j = 0; j < W; ++j) {
            if (B[i][j] == '1') ds.unite(get_id(i, j), get_id(i + 1, j)); 
        }
        bad[i + 1] = bad[i] + (count(B[i].begin(), B[i].end(), '1') == 0); 
    }

    for (int i = 0; i < H; ++i) {
        // cin >> C[i];  
        int c; cin >> c; 

        for (int t = 0; t < 2; ++t) {
            last[t][i] = i ? last[t][i - 1] : -1; 
        }
        last[c - 1][i] = i; 

        for (int j = 0; j < W; ++j) {
            best[i] = max(best[i], ds.bot(W * i + j) / W); 
        }
    }

    for (int i = 0; i < H; i++) {
        jmp[i][0][0] = i; 
        jmp[i][0][1] = (last[i][0] == -1 ? i : best[last[i][0]]); 
    }

    for (int b = 1; b < 20; ++b) {
        for (int i = 0; i < H; ++i) {
            jmp[i][b][0] = max(jmp[jmp[i][b - 1][0]][b - 1][1], jmp[jmp[i][b - 1][1]][b - 1][0]);           
            jmp[i][b][1] = jmp[jmp[i][b - 1][1]][b - 1][1]; 

            int pos = jmp[i][b - 1][0];
            pos = max(pos, max(best[pos], jmp[pos][1][1])); 
            pos = jmp[pos][b - 1][0];   

            jmp[i][b][1] = max({jmp[i][b][0], jmp[i][b][1], pos}); 
        }       
    }

    while (Q--) {
        int k; 
        cin >> k; 
        vector<int> s(k); 
        for (int i = 0; i < k; ++i) {
            int x, y; 
            cin >> x >> y; 
            x--; y--; 
            s[i] = ds.get_parent(x * W + y); 
        }
        sort(s.begin(), s.end()); 
        s.erase(unique(s.begin(), s.end()), s.end()); 
        k = s.size(); 
        if (k == 1) {
            cout << "0\n"; continue; 
        }
        vector<pair<int, int>> segs(k); 
        for (int i = 0; i < k; ++i) {
            segs[i] = {ds.top(s[i]) / W, ds.bot(s[i]) / W}; 
        }
        sort(segs.begin(), segs.end()); 
        if (bad[segs[k - 1].second] - bad[segs[0].first] > 0) {
            cout << "-1\n"; continue; 
        }

        // state -> (x, r, c) => 
        // first x are connected
        // furthest reaching is r 
        // cost is c 
        // only consider 3 values of r, each have val of c 

        vector<int> rb(k); // rb[i] = minimum value of r in range from i <=> k - 1
        for (int i = k - 1; i >= 0; --i) {
            rb[i] = segs[i].second; 
            if (i + 1 < k) rb[i] = min(rb[i], rb[i + 1]); 
        }

        // store cost, right 
        vector<vector<array<int, 2>>> dp(k); 
        dp[0].push_back({0, segs[0].second}); 

        auto clean = [&] (int i) {
            sort(dp[i].begin(), dp[i].end()); 
            while (dp[i].back()[0] > dp[i][0][0] + 2) dp[i].pop_back(); 
            vector<array<int, 2>> res;
            for (auto [c, r]: dp[i]) {
                if (res.size() && res.back()[0] == c && r >= res.back()[1]) res.pop_back(); 
                res.push_back({c, r}); 
            }
            dp[i] = res; 
        }; 
        int reach = 0; 
        for (int i = 0; i < k - 1; ++i) {
            if (!dp[i].size()) continue; 
            clean(i); 

            vector<array<int, 2>> todo; 
            for (auto [cost, right]: dp[i]) {
                for (int t = 0; t < 2; ++t) {
                    int pos = last[t][right]; 
                    if (pos < segs[0].first) continue; 
                    todo.push_back({cost + 1 + t, best[pos]}); 
                }
            }
            for (auto x: todo) dp[i].push_back(x); 
            clean(i); 

            for (auto [cost, right] : dp[i]) {
                int max_right = max(right, rb[i + 1]); 

                for (int t = 0; t < 2; ++t) {
                    int pos = last[t][max_right]; 
                    if (pos < segs[0].first) continue; 
                    // find last effected position 

                    int lo = 0, hi = k - 1; 
                    while (lo < hi) {
                        int md = (lo + hi + 1) / 2; 
                        if (segs[md].first <= pos) {
                            lo = md; 
                        } else {
                            hi = md - 1; 
                        }
                    }
                    if (lo > i) { // immediately one stab connects current with some new component 
                        reach = max(reach, lo); 
                        dp[lo].push_back({cost + t + 1, best[pos]}); 
                    } else { 
                        // keep stabbing futhest (either 1 or 2) 
                        // thus use bin lifting 
                        // to 1 stab before connecting new 
                        // then (manaully) use one stab to transition 
                        //
                    }
                }
            }
        }
        int ans = 1e9; 
        for (auto x: dp.back()) {
            ans = min(ans, x[1]); 
        }
        cout << ans << '\n'; 
    }


}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 11
• Subtask 5: 0 / 6
• Subtask 6: 0 / 12
• Subtask 7: 0 / 26
• Subtask 8: 0 / 14