Submission #1182397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182397		patgra	Road Service 2 (JOI24_ho_t5)	C++20	60 / 100	1063 ms	382272 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr int maxn = 1e6 + 7, maxLog = dbg ? 3 : 23, inf = 1e9 + 8;
int h, w, q, n;
vector<int> graf[maxn];
int component[maxn], top[maxn], bottom[maxn];
int jp[maxn][maxLog];
pair<int, int> jp2[maxn][maxLog]; // { jump 2^j , jump 2^j - 1 }
int rowCosts[maxn];
bool twos;
int cToRow1[maxn], cToRow2[maxn], rowToC[maxn];
int secondRTC[maxn];
int lowestSon1[maxn], lowestSon2[maxn];

vector<vector<int>> xd1, xd2;

bool cmpBottom(int a, int b) {
    if(bottom[a] == bottom[b]) return top[a] < top[b];
    return bottom[a] < bottom[b];
}

bool cmpTop(int a, int b) {
    if(top[a] == top[b]) return bottom[a] < bottom[b];
    return top[a] < top[b];
}

void input() {
    cin >> h >> w >> q;
    char c;
    xd1.resize(h, vector<int>(w - 1));
    rep(i, 0, h) rep(j, 0, w - 1) cin >> c, (c == '1' ? graf[i * w + j].pb(i * w + j + 1), graf[i * w + j + 1].pb(i * w + j), 0 : 0), xd1[i][j] = c == '1';
    xd2.resize(h - 1, vector<int>(w));
    rep(i, 0, h - 1) rep(j, 0, w) cin >> c, (c == '1' ? graf[i * w + j].pb(i * w + j + w), graf[i * w + j + w].pb(i * w + j), 0 : 0), xd2[i][j] = c == '1';
    rep(i, 0, h) cin >> rowCosts[i], twos = twos || (rowCosts[i] == 2);
}

void dfsComponents(int v, int c) {
    component[v] = c;
    top[c] = min(top[c], v / w);
    bottom[c] = max(bottom[c], v / w);
    repIn(u, graf[v]) if (!component[u]) dfsComponents(u, c);
}
void calcComponents() {
    top[0] = bottom[0] = -1;
     DC << "Components: " << eol;
    rep(i, 0, h) rep(j, 0, w) if (!component[i * w + j]) {
        n++;
        top[n] = bottom[n] = i;
        dfsComponents(i * w + j, n);
         DC << " comp " << n << " from " << i << ' ' << j << "  ->  top " << top[n] << " bottom " << bottom[n] << eol;
    }
}

void calcLowest() {
    rep(i, 1, n + 1) cToRow1[i] = cToRow2[i] = -1;
    repD(i, h - 1, -1) {
        rep(j, 0, w) {
            auto c = component[i * w + j];
            if (rowToC[i] == 0 || bottom[c] > bottom[rowToC[i]]) secondRTC[i] = rowToC[i], rowToC[i] = c;
            else if (secondRTC[i] == 0 || bottom[c] > bottom[secondRTC[i]]) secondRTC[i] = c;
            if (rowCosts[i] == 1) if (cToRow1[c] == -1) cToRow1[c] = i;
            if (rowCosts[i] == 2) if (cToRow2[c] == -1) cToRow2[c] = i;
        }
    }
    //return;
    DEBUG {
        DC << "Component to row: " << eol;
        rep(i, 1, n + 1) DC << " " << i << ":  1 -> " << cToRow1[i] << "  2 -> " << cToRow2[i] << eol;
        DC << "Row to component: " << eol;
        rep(i, 0, h) DC << " " << i << " -> " << rowToC[i] << eol;
    }
}

void calcLowestSon() {
    rep(i, 1, n + 1) {
        if(cToRow1[i] == -1) {
            if(cToRow2[i] == -1) lowestSon1[i] = maxn - 1;
            else {
                if(bottom[rowToC[cToRow2[i]]] <= bottom[i]) lowestSon1[i] = maxn - 1;
                else lowestSon1[i] = 0;
            }
        }
        else {
            if(bottom[rowToC[cToRow1[i]]] <= bottom[i]) {
                if(bottom[rowToC[cToRow2[i]]] <= bottom[i]) lowestSon1[i] = maxn - 1;
                else lowestSon1[i] = 0;
            }
            else {
                lowestSon1[i] = rowToC[cToRow1[i]];
            }
        }
    }

    rep(i, 1, n + 1) {
        if(cToRow2[i] == -1) {
            if(cToRow1[i] == -1) lowestSon2[i] = maxn - 1;
            else {
                if(bottom[rowToC[cToRow1[i]]] <= bottom[i]) lowestSon2[i] = maxn - 1;
                else lowestSon2[i] = 0;
            }
        }
        else {
            if(bottom[rowToC[cToRow2[i]]] <= bottom[i]) {
                if(bottom[rowToC[cToRow1[i]]] <= bottom[i]) lowestSon2[i] = maxn - 1;
                else lowestSon2[i] = 0;
            }
            else {
                lowestSon2[i] = rowToC[cToRow2[i]];
            }
        }
    }

    bottom[maxn - 1] = inf;
    // return;
    DEBUG {
        DC << "LowestSons: " << eol;
        rep(i, 1, n + 1) DC << " " << i << "  ls1 " << lowestSon1[i] << "  ls2 " << lowestSon2[i] << eol;
    }
}

void calcJP() {
    rep(i, 1, n + 1) jp[i][0] = lowestSon1[i];
    rep(k, 1, maxLog) rep(i, 1, n + 1) jp[i][k] = jp[jp[i][k - 1]][k - 1];
}

void calcJP2() {
    rep(i, 1, n + 1) jp2[i][0] = {lowestSon1[i], i};
    rep(i, 1, n + 1) jp2[i][1] = {max(lowestSon1[lowestSon1[i]], lowestSon2[i], cmpBottom), lowestSon1[i]};
    rep(k, 2, maxLog) rep(i, 1, n + 1) jp2[i][k] = {max(jp2[jp2[i][k - 1].first][k - 1].first, jp2[lowestSon2[jp2[i][k - 1].second]][k - 1].second, cmpBottom), max(jp2[jp2[i][k - 1].second][k - 1].first, jp2[jp2[i][k - 1].first][k - 1].second, cmpBottom)};
    DEBUG {
        DC << "JP2: " << eol;
        rep(i, 1, n + 1) {
            DC << ' ' << i << ":  ";
            rep(k, 0, maxLog) DC << "{" << jp2[i][k].first << ' ' << jp2[i][k].second << "}  ";
            DC << eol;
        }
    }
}

pair<int, int> jump(int v, int u) {
    DC << "jump " << v << ' ' << u << eol << ' ';
    int ans = 0;
    repD(k, maxLog - 1, -1) if (jp[v][k] && bottom[jp[v][k]] < top[u]) {
        v = jp[v][k], ans += 1 << k;
        DC << v << "(" << (1 << k) << ") ";
    }
    DC << eol;
    return {v, ans};
}

pair<pair<int, int>, int> jump2(int v, int vm1, int u) {
    DC << "  Jumping2 from " << v << " to " << u << eol;
    int there = v, thereM1 = vm1;
    int cnt = 0;
    repD(k, maxLog - 1, -1) if(jp2[there][k].first && bottom[jp2[there][k].first] < top[u]) {
        auto prv = there;
        there = max(jp2[there][k].first, jp2[lowestSon2[thereM1]][k].second, cmpBottom);
        thereM1 = max(jp2[thereM1][k].first, jp2[prv][k].second, cmpBottom);
        cnt += (1 << k);
    }
    DC << "   -> " << there << ' ' << thereM1 << "  " << cnt << eol;
    return {{there, thereM1}, cnt};
}

int query(vector<int>& V) {
    int ans = 0;
    ranges::sort(V, cmpBottom);
    int last = -1;
    int v = V[0];

    if(!twos) rep(i, 1, (int)V.size()) {
        const auto& u = V[i];
        DC << "Jumping from " << v << " to " << u << "  ;  last = " << last << eol;
        if (v == u) DC << " skip" << eol;
        if (v == u) continue;
        if (last >= top[u] && last <= bottom[u]) DC << " skip" << eol;
        if (last >= top[u] && last <= bottom[u]) continue;
        if (v == 0) return -1;
        if (bottom[v] >= top[u]) {
            if (bottom[u] >= bottom[v]) last = (cToRow1[v] >= top[u]) ? cToRow1[v] : cToRow2[v];
            else last = (cToRow1[u] >= top[v]) ? cToRow1[u] : cToRow2[u];
            v = rowToC[last];
            ans += rowCosts[last];
            DC << " zachodza" << eol;
            continue;
        }
        auto [vv, cost] = jump(v, u);
        v = lowestSon1[vv], ans += cost;
        if (top[u] > bottom[v]) return -1;
        ans += 2;
        if (bottom[u] >= bottom[v]) {
            last = bottom[v];
            v = lowestSon1[v];
        }
        else {
            last = bottom[u];
            v = lowestSon1[u];
        }
    }

    if(twos) {
        vector<pair<int, int>> dp;
        vector<int> tmp;
        rep(i, 0, (int)V.size()) if(((!i || V[i - 1] != V[i]) && (i == (int)V.size() - 1 || V[i + 1] != V[i])) || (i && V[i - 1] == V[i] && (i == (int)V.size() - 1 || V[i + 1] != V[i]))) tmp.pb(V[i]);
        swap(tmp, V);
        DC << " V: ";
        repIn(i, V) DC << i << ' ';
        DC << eol;
        dp.pb({1, V[0]});
        ans = 0;
        while(!dp.empty() && dp.back().first != (int)V.size()) {
            if(dp.back().second == maxn - 1) dp.back().second = dp[dp.size() - 2].second;
            if((dp.size() > 2 && ((dp.back() == dp[dp.size() - 3] && dp.back() == dp[dp.size() - 2])))) { ans = -1; break; }
            pair<int, int> toPb = {-1, -1};

            auto [lastVi, lastAll] = dp.back();
            DC << " dp[" << ans << "] = {" << lastVi << ' ' << lastAll << "}" << eol;
            auto lastV = V[lastVi];
            auto topNxtV = top[lastV];
            auto botNxtV = bottom[lastV];
            auto botAll = bottom[lastAll];
            if(topNxtV <= botAll) {
                //  use lowest available to get as many from V as possible
                int myRow = -1;
                if(botNxtV <= botAll) myRow = cToRow1[lastV];
                else myRow = cToRow1[lastAll];
                if(myRow >= 0) {
                    while(lastVi < (int)V.size() && top[V[lastVi]] <= myRow && bottom[V[lastVi]] >= myRow) lastVi++;
                    toPb = max(toPb, pair{lastVi, rowToC[myRow]});
                }
            }
            else if(lastAll && dp.size() > 1 && dp.back().first == dp[dp.size() - 2].first) {
                lastVi = dp.back().first, lastAll = dp.back().second;
                auto nxtV = V[lastVi];
                auto [wher, cost] = jump2(lastAll, dp[dp.size() - 2].second, nxtV);
                auto [where, whereM1] = wher;
                if(cost > 1 && pair{lastVi, whereM1} != dp.back()) {
                    DC << " --dp[" << ans + cost - 1 << "] = {" << lastVi << ' ' << whereM1 << "}" << eol;
                    dp.pb({lastVi, whereM1});
                }
                if(cost > 0) {
                    DC << " -dp[" << ans + cost - 1 << "] = {" << lastVi << ' ' << where << "}" << eol;
                    dp.pb({lastVi, where});
                }
                ans += cost;
                if(cost != 0) continue;
            }

            //  use lowest one to get to lower all
            toPb = max(toPb, pair{dp.back().first, lowestSon1[lastAll]});

            if(dp.size() == 1) {
                dp.pb(toPb);
                ans++;
                continue;
            }

            // same but move by two
            lastVi = dp[dp.size() - 2].first, lastAll = dp[dp.size() - 2].second;
            lastV = V[lastVi];
            topNxtV = top[lastV];
            botNxtV = bottom[lastV];
            botAll = bottom[lastAll];
            if(topNxtV <= botAll) {
                //  use lowest available to get as many from V as possible
                int myRow = -1;
                if(botNxtV <= botAll) myRow = cToRow2[lastV];
                else myRow = cToRow2[lastAll];
                if(myRow >= 0) {
                    while(lastVi < (int)V.size() && top[V[lastVi]] <= myRow && bottom[V[lastVi]] >= myRow) lastVi++;
                    toPb = max(toPb, pair{lastVi, rowToC[myRow]});
                }
            }
            //  use lowest one to get to lower all
            toPb = max(toPb, pair{dp[dp.size() - 2].first, lowestSon2[lastAll]});

            dp.pb(toPb);
            ans++;
        }
        if(!dp.empty()) DC << " dp[" << dp.size() - 1 << "] = {" << dp.back().first << ' ' << dp.back().second << "}" << eol;
    }

    return ans;
}

void processQueries() {
    int t, a, b;
    vector<int> V;
    rep(i, 0, q) {
        DC << "Query " << i << eol;
        cin >> t;
        V.resize(t);
        rep(j, 0, t) cin >> a >> b, V[j] = component[(a - 1) * w + b - 1];
        cout << query(V) << '\n';
    }
}

void visualise() {
    rep(i, 0, h) { 
        rep(j, 0, 2 * w) {
            if(j % 2 == 0) {
                DC << (i && xd2[i - 1][j / 2] ? '|' : '.');
            }
            else {
                DC << (j / 2 < xd1[i].size() && xd1[i][j / 2] ? '_' : ' ');
            }
        } 
        DC << "\t\t" << rowCosts[i] << "\t\t";
        rep(j, 0, w) {
            auto c = component[i * w + j];
            DC << c;
            if(c / 10) { DC << " "; }
            else DC << "  ";
        }
        DC << eol; 
    }
}


int main() {
    input();
    twos=true;
    calcComponents();
    calcLowest();
    calcLowestSon();
    calcJP();
    calcJP2();
    DEBUG visualise();
    processQueries();
    return 0;
}

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