Submission #1129967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129967		patgra	Road Service 2 (JOI24_ho_t5)	C++20	27 / 100	520 ms	249528 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;
int h, w, q, n;
vector<int> graf[maxn];
int component[maxn], top[maxn], bottom[maxn];
int jp[maxn][maxLog];
int rowCosts[maxn];

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);
}

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() {
    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 << "Component " << 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 rep(i, 1, n + 1) DC << "cToRow1[" << i << "] = " << cToRow1[i] << "  cToRow2 = " << cToRow2[i] << eol;
    DEBUG rep(i, 0, h) DC << "rowToC[" << i << "] = " << rowToC[i] << eol;
}
void calcJP() {
    rep(i, 1, n + 1) jp[i][0] = cToRow1[i] == -1 ? 0 : (rowToC[cToRow1[i]] == i ? 0 : rowToC[cToRow1[i]]);
    rep(i, 1, n + 1) {
        auto a = jp[jp[i][0]][0], b = cToRow2[i] == -1 ? 0 : (rowToC[cToRow2[i]] == i ? 0 : rowToC[cToRow2[i]]);
        if (a == 0) {jp[i][1] = b; continue;}
        if (b == 0) {jp[i][1] = a; continue;}
        if (bottom[a] > bottom[b]) jp[i][1] = a;
        else jp[i][1] = b;
    }
    rep(k, 2, maxLog) rep(i, 1, n + 1) jp[i][k] = jp[jp[i][k - 1]][k - 1];
    DEBUG {
        rep(k, 0, 3) rep(i, 1, n + 1) DC << "jp[" << i << "][" << k << "] = " << jp[i][k] << eol;
    }
}

vector<pair<int, int>> dijGraf[5 * maxn];
void makeGraf() {
    rep(i, 0, h) rep(j, 0, w) if (j == 0 || component[i * w + j] != component[i * w + j - 1]) dijGraf[4 * maxn + i].push_back({component[i * w + j], 0}), dijGraf[component[i * w + j]].push_back({4 * maxn + i, rowCosts[i]});
}
bool vis[maxn * 5];
int queryBrut(int V, int U) {
    rep(i, 1, n + 1) vis[i] = false;
    rep(i, 0, h) vis[4 * maxn + i] = false;
    priority_queue<pair<int, int>> Q;
    Q.push({0, V});
    while (!Q.empty()) {
        auto [mc, mv] = Q.top(); Q.pop();
        mc = -mc;
        if (vis[mv]) continue;
        vis[mv] = true;
        if (mv == U) return mc;
        repIn2(u, c, dijGraf[mv]) if (!vis[u]) Q.push({-mc - c, u});
    }
    return -1;
}

int lmao(int v, int u, int ans) {
    if (cToRow1[v] != -1 && top[u] <= cToRow1[rowToC[cToRow1[v]]] && cToRow1[u] != -1) {
        DC << "." << eol;
        return ans + 2;
    }
    if (cToRow1[v] != -1 && top[u] <= cToRow2[rowToC[cToRow1[v]]] && cToRow2[u] != -1) {
        DC << "," << eol;
        return ans + 3;
    }
    if (cToRow2[v] != -1 && top[u] <= cToRow1[rowToC[cToRow2[v]]] && cToRow1[u] != -1) {
        DC << '_' << eol;
        return ans + 3;
    }
    if (cToRow2[v] != -1 && top[u] <= cToRow2[rowToC[cToRow2[v]]] && cToRow2[u] != -1) {
        DC << ';' << eol;
        return ans + 4;
    }
    DC << "chuj" << eol;
    return 1e9;
}
int query(int v, int u) {
    if (bottom[v] > bottom[u]) swap(u, v);
    if (u == v) return 0;
    if (bottom[v] >= top[u]) return 1 + (cToRow1[v] < top[u]);
    int ans = 0;
    DC << "query " << v << ' ' << u << eol << ' ';
    repD(k, maxLog - 1, -1) if (jp[v][k] && bottom[jp[v][k]] < top[u] && (bottom[jp[v][0]] < top[u]) && (k == 0 || jp[v][k - 1] != jp[v][k])) {
        v = jp[v][k], ans += 1 << k;
        DC << v << "(" << (1 << k) << ") ";
    }
    // DC << ".";
    int xd1 = lmao(v, u, ans), xd2 = 1e9, xd3 = 1e9;
    if (jp[v][0]) xd2 = lmao(jp[v][0], u, ans + 1);
    if (jp[v][1]) xd3 = lmao(jp[v][1], u, ans + 2);
    auto xdd = min(xd1,  min(xd2, xd3));
    if (xdd == 1e9) return -1;
    return xdd;
}

void processQueries(bool brut = false) {
    if (brut) makeGraf();
    int t, a, b, c, d;
    rep(i, 0, q) {
        // TODO: more vertices
        scanf("%d%d%d%d%d", &t, &a, &b, &c, &d);
        a--; b--; c--; d--;
        if (brut) printf("%d\n", queryBrut(component[a * w + b], component[c * w + d]));
        else printf("%d\n", query(component[a * w + b], component[c * w + d]));
    }
}

int main() {
    input();
    calcComponents();
    calcLowest();
    calcJP();
    processQueries();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void input()':
Main.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d%d%d", &h, &w, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     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:28:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     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:29:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     rep(i, 0, h) scanf("%d", rowCosts + i);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void processQueries(bool)':
Main.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%d%d%d%d%d", &t, &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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