oj.uz

Submission #967388

# Submission time Handle Problem Language Result Execution time Memory
967388 2024-04-22T04:05:51 Z Pring Wombats (IOI13_wombats) C++17
28 / 100
 9641 ms 17756 KB 
#include <bits/stdc++.h>
#ifndef MIKU
#include "wombats.h"
#endif
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

namespace {
    const int MXN = 105, MXM = 200;
    int n, m;
    int h[MXN][MXM], v[MXN][MXM];
    vector<pii> edge[MXN * MXM];
    int dis[MXN * MXM];

    void build() {
        FOR(i, 0, n * m) edge[i].clear();
        FOR(i, 0, n) FOR(j, 0, m - 1) {
            edge[i * m + j].push_back(mp(h[i][j], i * m + j + 1));
            edge[i * m + j + 1].push_back(mp(h[i][j], i * m + j));
        }
        FOR(i, 0, n - 1) FOR(j, 0, m) {
            edge[i * m + j].push_back(mp(v[i][j], (i + 1) * m + j));
        }
    }

    void DIJKSTRA(int sr) {
        fill(dis, dis + n * m, -1);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push(mp(0, sr));
        while (pq.size()) {
            auto [len, id] = pq.top();
            pq.pop();
            if (dis[id] != -1) continue;
            dis[id] = len;
            for (auto &[w, i] : edge[id]) {
                if (dis[i] != -1) continue;
                pq.push(mp(len + w, i));
            }
        }
    }
}

void init(int R, int C, int H[][200], int V[][200]) {
    n = R;
    m = C;
    FOR(i, 0, n) copy(H[i], H[i] + m - 1, h[i]);
    FOR(i, 0, n - 1) copy(V[i], V[i] + m, v[i]);
    // build();
    // FOR(i, 0, m) {
    //     DIJKSTRA(i);
    //     copy(dis + (n - 1) * m, dis + (n * m), ans[i]);
    // }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
}

int escape(int V1, int V2) {
    build();
    DIJKSTRA(V1);
    return dis[(n - 1) * m + V2];
}

#ifdef MIKU
int hh[MXN][MXM], vv[MXN][MXM];
void miku() {
    int nn, mm;
    cin >> nn >> mm;
    FOR(i, 0, nn) FOR(j, 0, mm - 1) cin >> hh[i][j];
    FOR(i, 0, nn - 1) FOR(j, 0, mm) cin >> vv[i][j];
    init(nn, mm, hh, vv);
    int ee;
    cin >> ee;
    while (ee--) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, q, w;
            cin >> p >> q >> w;
            changeH(p, q, w);
        } else if (t == 2) {
            int p, q, w;
            cin >> p >> q >> w;
            changeV(p, q, w);
        } else {
            int v1, v2;
            cin >> v1 >> v2;
            cout << escape(v1, v2) << '\n';
        }
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}
#endif

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 13656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2560 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 23 ms 4648 KB Output is correct
5 Correct 13 ms 4648 KB Output is correct
6 Correct 16 ms 4648 KB Output is correct
7 Correct 17 ms 4444 KB Output is correct
8 Correct 17 ms 4444 KB Output is correct
9 Correct 20 ms 4644 KB Output is correct
10 Correct 18 ms 4440 KB Output is correct
11 Correct 9641 ms 5572 KB Output is correct
12 Correct 18 ms 4440 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 5260 KB Output is correct
2 Correct 189 ms 5464 KB Output is correct
3 Correct 170 ms 5364 KB Output is correct
4 Correct 168 ms 5356 KB Output is correct
5 Correct 162 ms 5212 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 175 ms 5396 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 17756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 5208 KB Output is correct
2 Correct 190 ms 5468 KB Output is correct
3 Correct 167 ms 5212 KB Output is correct
4 Correct 164 ms 5212 KB Output is correct
5 Correct 167 ms 5364 KB Output is correct
6 Runtime error 9 ms 17752 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 5264 KB Output is correct
2 Correct 188 ms 5212 KB Output is correct
3 Correct 164 ms 5360 KB Output is correct
4 Correct 166 ms 5360 KB Output is correct
5 Correct 164 ms 5208 KB Output is correct
6 Runtime error 10 ms 17756 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -