Submission #1131202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131202		patgra	Road Service 2 (JOI24_ho_t5)	C++20	48 / 100	492 ms	160344 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)

#define ll long long

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

using namespace std;

constexpr int maxn = 1e6 + 7, maxLog = 21, 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;

void input() {
    scanf("%d%d%d", &h, &w, &q);
    char c;
    rep(i, 0, h) rep(j, 0, w - 1) scanf(" %c", &c), (c == '1' ? graf[i * w + j].push_back(i * w + j + 1), graf[i * w + j + 1].push_back(i * w + j), 0 : 0);
    rep(i, 0, h - 1) rep(j, 0, w) scanf(" %c", &c), (c == '1' ? graf[i * w + j].push_back(i * w + j + w), graf[i * w + j + w].push_back(i * w + j), 0 : 0);
    rep(i, 0, h) scanf("%d", 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;
    }
}

int cToRow1[maxn], cToRow2[maxn], rowToC[maxn];
int secondRTC[maxn];
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;
        }
    }
    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;
    }
}
int lowestSon1[maxn], lowestSon2[maxn];
void calcLowestSon() {
    rep(i, 1, n + 1) lowestSon1[i] = (cToRow1[i] == -1 || rowToC[cToRow1[i]] == i ? 0 : rowToC[cToRow1[i]]), lowestSon2[i] = (cToRow2[i] == -1 || rowToC[cToRow2[i]] == i ? 0 : rowToC[cToRow2[i]]);
    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(k, 1, maxLog) rep(i, 1, n + 1) {
        int a = jp2[jp2[i][k - 1].first][k - 1].first;
        int b = jp2[lowestSon2[jp2[i][k - 1].second]][k - 1].second;
        if (a == 0) jp2[i][k].first = b;
        else if (b == 0) jp2[i][k].first = a;
        else if (bottom[a] > bottom[b]) jp2[i][k].first = a;
        else jp2[i][k].first = b;

        a = jp2[jp2[i][k - 1].first][k - 1].second;
        b = jp2[jp2[i][k - 1].second][k - 1].first;
        if (a == 0) jp2[i][k].second = b;
        else if (b == 0) jp2[i][k].second = a;
        else if (bottom[a] > bottom[b]) jp2[i][k].second = a;
        else jp2[i][k].second = b;
    }

    DEBUG {
        DC << "JP2:" << eol;
        rep(i, 1, n + 1) {
            DC << " From " << i << eol;
            rep(k, 0, 4) DC << "  2^" << k << "  ->  " << jp2[i][k].first << ' ' << jp2[i][k].second << 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> jumpTwos(int v, int u) {

    DC << " jumping from " << v << " to " << u << eol;
    int v1 = v, v2 = v, moves = 0;
    repD(k, maxLog - 1, -1) {
        if (!jp2[v2][k].first) continue;

        int a = jp2[v2][k].first;
        int b = jp2[lowestSon2[v1]][k].second;
        if (v1 == v2) b = 0;
        int og2 = v2;
        if (a == 0) v2 = b;
        else if (b == 0) v2 = a;
        else if (bottom[a] > bottom[b]) v2 = a;
        else v2 = b;

        if (bottom[v2] >= top[u]) {
            v2 = og2;
            continue;
        }

        a = jp2[v1][k].first;
        if (v1 == og2 && k == 0) a = v1;
        b = jp2[og2][k].second;
        if (a == 0) v1 = b;
        else if (b == 0) v1 = a;
        else if (bottom[a] > bottom[b]) v1 = a;
        else v1 = b;

        moves += 1 << k;

        DC << "  jumped " << (1 << k) << " into " << v2 << " ( or -1 to " << v1 << " )" << eol;
    }

    DC << " walking now" << eol;
    if (v1 == v2) {
        v2 = lowestSon1[v1];
        moves++;
    }
    while ((v1 != 0 && (v2 == 0 || bottom[v2] < top[u])) || (v2 != 0 && bottom[v2] < top[u])) {
        DC << "  " << v1 << ' ' << v2 << eol;
        auto v3 = (bottom[lowestSon1[v2]] > bottom[lowestSon2[v1]]) ? lowestSon1[v2] : lowestSon2[v1];
        v1 = v2;
        v2 = v3;
        moves++;
    }
    DC << "  " << v1 << ' ' << v2 << eol;

    return {{v1, v2}, moves};
}

bool cmpBottom(int a, int b) {
    return bottom[a] < bottom[b];
}
int query(vector<int>& V) {
    int ans = 0;
    ranges::sort(V, cmpBottom);
    int last = -1;
    int v = V[0];
    rep(i, 1, 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;
        }
        if (!twos) {
            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];
            }
        }
        else {
            auto [vs, initialMoves] = jumpTwos(v, u);
            auto [v1, v2] = vs;

            int moves1 = inf, last1 = inf, moves2 = inf, last2 = inf;

            if (v2 != 0) {
                if (bottom[u] > bottom[v2]) {
                    if (cToRow1[v2] >= top[u]) moves2 = initialMoves + 1, last2 = cToRow1[v2];
                    else moves2 = initialMoves + 2, last2 = cToRow2[v2];
                }
                else {
                    if (cToRow1[u] >= top[v2]) moves2 = initialMoves + 1, last2 = cToRow1[u];
                    else moves2 = initialMoves + 2, last2 = cToRow2[u];
                }
            }

            if (cToRow2[v1] != -1) {
                v1 = rowToC[cToRow2[v1]];
                if (v1 != 0 && bottom[v1] >= top[u]) {
                    initialMoves++;
                    if (bottom[u] > bottom[v1]) {
                        if (cToRow1[v1] >= top[u]) moves1 = initialMoves + 1, last1 = cToRow1[v1];
                        else moves1 = initialMoves + 2, last1 = cToRow2[v1];
                    }
                    else {
                        if (cToRow1[u] >= top[v1]) moves1 = initialMoves + 1, last1 = cToRow1[u];
                        else moves1 = initialMoves + 2, last1 = cToRow2[u];
                    }
                    initialMoves--;
                }
            }

            if (moves1 == inf && moves2 == inf) return -1;

            // TODO: What if t > 2? Pay one more for greater `last`???
            if (moves1 < moves2) {
                ans += moves1;
                last = last1;
            }
            else if (moves1 > moves2) {
                ans += moves2;
                last = last2;
            }
            else {
                ans += moves1;
                last = max(last1, last2);
            }

            v = rowToC[last];
        }
    }
    return ans;
}

void processQueries() {
    int t, a, b;
    vector<int> V;
    rep(i, 0, q) {
        scanf("%d", &t);
        V.resize(t);
        rep(j, 0, t) scanf("%d%d", &a, &b), V[j] = component[(a - 1) * w + b - 1];
        printf("%d\n", query(V));
    }
}

int main() {
    input();
    calcComponents();
    calcLowest();
    calcLowestSon();
    if (twos) calcJP2();
    calcJP();
    processQueries();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void input()':
Main.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d%d", &h, &w, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:29:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     rep(i, 0, h) rep(j, 0, w - 1) scanf(" %c", &c), (c == '1' ? graf[i * w + j].push_back(i * w + j + 1), graf[i * w + j + 1].push_back(i * w + j), 0 : 0);
      |                                   ~~~~~^~~~~~~~~~~
Main.cpp:30:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     rep(i, 0, h - 1) rep(j, 0, w) scanf(" %c", &c), (c == '1' ? graf[i * w + j].push_back(i * w + j + w), graf[i * w + j + w].push_back(i * w + j), 0 : 0);
      |                                   ~~~~~^~~~~~~~~~~
Main.cpp:31:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     rep(i, 0, h) scanf("%d", rowCosts + i), twos = twos || (rowCosts[i] == 2);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void processQueries()':
Main.cpp:268:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  268 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~
Main.cpp:270:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  270 |         rep(j, 0, t) scanf("%d%d", &a, &b), V[j] = component[(a - 1) * w + b - 1];
      |                      ~~~~~^~~~~~~~~~~~~~~~

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