oj.uz

Submission #1035600

# Submission time Handle Problem Language Result Execution time Memory
1035600 2024-07-26T12:21:51 Z c2zi6 Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 262144 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "wombats.h"

const int MAXC = 200;

int n, m;
struct PART {
    int d[MAXC][MAXC];
    PART() {
        rep(i, m) rep(j, m) d[i][j] = 2e9;
    }
    void add(const PART& b) {
        PART c;
        rep(u, m) rep(v, m) rep(mid, m) {
            setmin(c.d[u][v], d[u][mid] + b.d[mid][v]);
        }
        rep(u, m) rep(v, m) d[u][v] = c.d[u][v];
    }
};
void combine(const PART& a, const PART& b) {
    PART c;
    rep(u, m) rep(v, m) rep(mid, m) {
        setmin(c.d[u][v], a.d[u][mid] + b.d[mid][v]);
    }
}
vector<PART> a;
PART answer;
VVI H, V;

void recalc() {
    a = vector<PART>(n);
    rep(u, n) {
        replr(i, 0, m-1) {
            int sum = 0;
            replr(j, i, m-1) {
                a[u].d[i][j] = sum + V[u][j];
                a[u].d[j][i] = sum + V[u][i];
                sum += H[u][j];
            }
        }
    }
    answer = a[0];
    replr(i, 1, n-1) answer.add(a[i]);
}

void init(int R, int C, int H_arg[5000][200], int V_arg[5000][200]) {
    n = R;
    m = C;

    H = V = VVI(n, VI(m));
    rep(i, n) rep(j, m-1) H[i][j] = H_arg[i][j];
    rep(i, n-1) rep(j, m) V[i][j] = V_arg[i][j];

    recalc();
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    recalc();
    /* ... */
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    recalc();
    /* ... */
}

int escape(int u, int v) {
    return answer.d[u][v];
}

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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4606 ms 57372 KB Output is correct
2 Correct 4848 ms 57400 KB Output is correct
3 Correct 4383 ms 57476 KB Output is correct
4 Correct 4487 ms 57396 KB Output is correct
5 Correct 4538 ms 55932 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 40 ms 2140 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9788 ms 17420 KB Output is correct
2 Correct 9765 ms 17148 KB Output is correct
3 Correct 9905 ms 17456 KB Output is correct
4 Correct 10032 ms 17456 KB Output is correct
5 Correct 9640 ms 17312 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Execution timed out 20086 ms 17200 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5238 ms 65740 KB Output is correct
2 Correct 4904 ms 67372 KB Output is correct
3 Correct 5030 ms 65800 KB Output is correct
4 Correct 5398 ms 67816 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11619 ms 17620 KB Output is correct
2 Correct 11090 ms 17152 KB Output is correct
3 Correct 9901 ms 17456 KB Output is correct
4 Correct 9474 ms 17460 KB Output is correct
5 Correct 9032 ms 17404 KB Output is correct
6 Correct 4762 ms 65808 KB Output is correct
7 Correct 4726 ms 67368 KB Output is correct
8 Correct 4984 ms 65888 KB Output is correct
9 Correct 5117 ms 66924 KB Output is correct
10 Correct 4651 ms 54356 KB Output is correct
11 Correct 4759 ms 55708 KB Output is correct
12 Correct 4718 ms 54564 KB Output is correct
13 Correct 4570 ms 55828 KB Output is correct
14 Correct 4653 ms 57240 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 704 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 42 ms 3472 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Execution timed out 20084 ms 17208 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9819 ms 17616 KB Output is correct
2 Correct 10103 ms 17152 KB Output is correct
3 Correct 10798 ms 17464 KB Output is correct
4 Correct 9532 ms 17456 KB Output is correct
5 Correct 9386 ms 17276 KB Output is correct
6 Correct 4901 ms 67460 KB Output is correct
7 Correct 5230 ms 67104 KB Output is correct
8 Correct 5017 ms 64304 KB Output is correct
9 Correct 5091 ms 67072 KB Output is correct
10 Correct 4509 ms 55888 KB Output is correct
11 Correct 4357 ms 58960 KB Output is correct
12 Correct 4671 ms 55884 KB Output is correct
13 Correct 4604 ms 55836 KB Output is correct
14 Correct 4721 ms 55856 KB Output is correct
15 Runtime error 319 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -