oj.uz

Submission #1036470

# Submission time Handle Problem Language Result Execution time Memory
1036470 2024-07-27T12:07:20 Z c2zi6 Wombats (IOI13_wombats) C++14
100 / 100
 4811 ms 190996 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;
const int PARTMAXVAL = 1e9;
const int GROUPSIZE = 15;

struct PART;
PART combine(PART& a, PART& b);

struct PART {
    int d[MAXC][MAXC];
    PART() {
        rep(i, MAXC) rep(j, MAXC) d[i][j] = PARTMAXVAL;
    }
    int* operator[](int i) {
        return d[i];
    }
    void combine(PART& b) {
        *this = ::combine(*this, b);
    }
};

int n, m;
VVI H, V;

PART combine(PART& a, PART& b) {
    PART c;
    int mid[MAXC][MAXC];
    reprl(d, +MAXC, -MAXC) rep(i, MAXC) {
        int j = i-d;
        if (j < 0 || j >= MAXC) continue;
        int mn = 0;
        int mx = MAXC-1;
        if (j-1 >= 0) mn = mid[i][j-1];
        if (i+1 < MAXC) mx = mid[i+1][j];
        mid[i][j] = mx;
        replr(m, mn, mx) {
            if (a[i][m] + b[m][j] < c[i][j]) {
                c[i][j] = a[i][m] + b[m][j];
                mid[i][j] = m;
            }
        }
    }
    return c;
}

void recalcpart(PART& p, int l) {
    if (l >= n) {
        p = PART();
        rep(i, MAXC) p[i][i] = 0;
        return;
    }
    replr(i, 0, m-1) {
        int sum = 0;
        replr(j, i, m-1) {
            p[i][j] = sum + V[l][j];
            p[j][i] = sum + V[l][i];
            sum += H[l][j];
        }
    }
}

struct SEGTREE {
    int n;
    vector<PART> tree;
    SEGTREE(){}
    SEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = vector<PART>(2*n);
        for (PART& p : tree) {
            rep(i, MAXC) p[i][i] = 0;
        }
    }
    void upd(int N, int L, int R, int i) {
        if (i < L || i > R) return;
        if (L == R) {
            bool f = true;
            PART tmp;
            replr(j, i*GROUPSIZE, (i+1)*GROUPSIZE-1) {
                recalcpart(tmp, j);
                if (f) tree[N] = tmp, f = false;
                else tree[N] = combine(tree[N], tmp);
            }
            return;
        }
        int M = (L + R) / 2;
        upd(2*N+1, L, M, i);
        upd(2*N+2, M+1, R, i);
        tree[N] = combine(tree[2*N+1], tree[2*N+2]);
    }
    void upd(int i) {
        upd(0, 0, n-1, i);
    }
} seg;

int gcnt;

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();*/
    int gcnt = (n+GROUPSIZE-1)/GROUPSIZE;
    seg = SEGTREE(gcnt);
    rep(i, gcnt) seg.upd(i);
}
 
void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    seg.upd(P/GROUPSIZE);
}
 
void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    seg.upd(P/GROUPSIZE);
}
 
int escape(int u, int v) {
    return seg.tree[0][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 3745 ms 168508 KB Output is correct
2 Correct 3614 ms 168532 KB Output is correct
3 Correct 3785 ms 171164 KB Output is correct
4 Correct 3955 ms 168272 KB Output is correct
5 Correct 3733 ms 168272 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 4 ms 1080 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 4 ms 1112 KB Output is correct
3 Correct 4 ms 1116 KB Output is correct
4 Correct 7 ms 1728 KB Output is correct
5 Correct 7 ms 1884 KB Output is correct
6 Correct 8 ms 1880 KB Output is correct
7 Correct 7 ms 1884 KB Output is correct
8 Correct 8 ms 2044 KB Output is correct
9 Correct 7 ms 1884 KB Output is correct
10 Correct 7 ms 1884 KB Output is correct
11 Correct 44 ms 4032 KB Output is correct
12 Correct 7 ms 1912 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 4440 KB Output is correct
2 Correct 404 ms 4444 KB Output is correct
3 Correct 438 ms 4444 KB Output is correct
4 Correct 415 ms 4440 KB Output is correct
5 Correct 400 ms 4444 KB Output is correct
6 Correct 4 ms 1120 KB Output is correct
7 Correct 4 ms 1188 KB Output is correct
8 Correct 7 ms 1116 KB Output is correct
9 Correct 1797 ms 4692 KB Output is correct
10 Correct 10 ms 1112 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3929 ms 172368 KB Output is correct
2 Correct 3620 ms 172368 KB Output is correct
3 Correct 3910 ms 172372 KB Output is correct
4 Correct 4210 ms 173660 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 4440 KB Output is correct
2 Correct 443 ms 4444 KB Output is correct
3 Correct 443 ms 4520 KB Output is correct
4 Correct 452 ms 4700 KB Output is correct
5 Correct 531 ms 4444 KB Output is correct
6 Correct 4393 ms 172428 KB Output is correct
7 Correct 4246 ms 172452 KB Output is correct
8 Correct 4274 ms 172472 KB Output is correct
9 Correct 4251 ms 173760 KB Output is correct
10 Correct 4297 ms 168516 KB Output is correct
11 Correct 4259 ms 168476 KB Output is correct
12 Correct 4471 ms 171168 KB Output is correct
13 Correct 4234 ms 168528 KB Output is correct
14 Correct 4107 ms 168520 KB Output is correct
15 Correct 4 ms 1116 KB Output is correct
16 Correct 4 ms 1236 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 7 ms 1912 KB Output is correct
19 Correct 7 ms 1920 KB Output is correct
20 Correct 7 ms 1884 KB Output is correct
21 Correct 7 ms 1884 KB Output is correct
22 Correct 7 ms 1908 KB Output is correct
23 Correct 7 ms 1912 KB Output is correct
24 Correct 7 ms 1884 KB Output is correct
25 Correct 46 ms 4172 KB Output is correct
26 Correct 7 ms 1880 KB Output is correct
27 Correct 1778 ms 4668 KB Output is correct
28 Correct 4086 ms 180052 KB Output is correct
29 Correct 4038 ms 177776 KB Output is correct
30 Correct 4120 ms 177744 KB Output is correct
31 Correct 4332 ms 181844 KB Output is correct
32 Correct 10 ms 1116 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 4440 KB Output is correct
2 Correct 371 ms 4444 KB Output is correct
3 Correct 419 ms 4444 KB Output is correct
4 Correct 442 ms 4440 KB Output is correct
5 Correct 429 ms 4444 KB Output is correct
6 Correct 3775 ms 172464 KB Output is correct
7 Correct 3650 ms 172208 KB Output is correct
8 Correct 3646 ms 172372 KB Output is correct
9 Correct 3657 ms 173668 KB Output is correct
10 Correct 3849 ms 168276 KB Output is correct
11 Correct 3748 ms 168528 KB Output is correct
12 Correct 3650 ms 171168 KB Output is correct
13 Correct 3484 ms 168276 KB Output is correct
14 Correct 3382 ms 168516 KB Output is correct
15 Correct 1840 ms 189820 KB Output is correct
16 Correct 4800 ms 190996 KB Output is correct
17 Correct 4 ms 1116 KB Output is correct
18 Correct 5 ms 1236 KB Output is correct
19 Correct 4 ms 1116 KB Output is correct
20 Correct 12 ms 1904 KB Output is correct
21 Correct 6 ms 1908 KB Output is correct
22 Correct 7 ms 1880 KB Output is correct
23 Correct 7 ms 1884 KB Output is correct
24 Correct 7 ms 1904 KB Output is correct
25 Correct 13 ms 1884 KB Output is correct
26 Correct 7 ms 1884 KB Output is correct
27 Correct 58 ms 4096 KB Output is correct
28 Correct 7 ms 1880 KB Output is correct
29 Correct 1661 ms 4444 KB Output is correct
30 Correct 4185 ms 180204 KB Output is correct
31 Correct 4313 ms 188240 KB Output is correct
32 Correct 4542 ms 188380 KB Output is correct
33 Correct 4109 ms 177744 KB Output is correct
34 Correct 4613 ms 184840 KB Output is correct
35 Correct 4197 ms 177800 KB Output is correct
36 Correct 4811 ms 184912 KB Output is correct
37 Correct 4233 ms 181804 KB Output is correct
38 Correct 4493 ms 189004 KB Output is correct
39 Correct 10 ms 1116 KB Output is correct
40 Correct 4797 ms 185076 KB Output is correct