oj.uz

답안 #1036464

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036464 2024-07-27T11:55:35 Z c2zi6 웜뱃 (IOI13_wombats) C++14
76 / 100
 5309 ms 125604 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 = 100;
const int PARTMAXVAL = 1e9;
const int GROUPSIZE = 10;

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) {
        int g = i/GROUPSIZE;
        if (g < L || g > R) return;
        if (L == R) {
            /*cout << "UPDATE ENDED AT LEAF " << N << endl;*/
            /*cout << "GROUP: " << g << endl;*/
            /*cout << "INDEX: " << i << endl;*/
            /*cout << "GROUP RANGE: " << g*GROUPSIZE << ".." << (g+1)*GROUPSIZE-1 << endl;*/
            bool f = true;
            PART tmp;
            replr(j, g*GROUPSIZE, (g+1)*GROUPSIZE-1) {
                /*cout << "RECALCULATED LAYER " << j << endl;*/
                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;

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();*/
    seg = SEGTREE((n+GROUPSIZE-1)/GROUPSIZE);
    rep(i, n) seg.upd(i);
}
 
void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    seg.upd(P);
}
 
void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    seg.upd(P);
}
 
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

# 결과 실행 시간 메모리 Grader output
1 Correct 4688 ms 45812 KB Output is correct
2 Correct 4607 ms 45828 KB Output is correct
3 Correct 4672 ms 48460 KB Output is correct
4 Correct 4579 ms 45772 KB Output is correct
5 Correct 4377 ms 45820 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 11 ms 852 KB Output is correct
5 Correct 14 ms 604 KB Output is correct
6 Correct 11 ms 852 KB Output is correct
7 Correct 11 ms 604 KB Output is correct
8 Correct 10 ms 848 KB Output is correct
9 Correct 11 ms 700 KB Output is correct
10 Correct 11 ms 852 KB Output is correct
11 Correct 58 ms 3040 KB Output is correct
12 Correct 11 ms 860 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 2396 KB Output is correct
2 Correct 160 ms 2396 KB Output is correct
3 Correct 197 ms 2396 KB Output is correct
4 Correct 187 ms 2396 KB Output is correct
5 Correct 198 ms 2396 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 436 ms 2436 KB Output is correct
10 Correct 3 ms 604 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4599 ms 49764 KB Output is correct
2 Correct 4681 ms 49756 KB Output is correct
3 Correct 4421 ms 50000 KB Output is correct
4 Correct 4747 ms 51120 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 2396 KB Output is correct
2 Correct 158 ms 2428 KB Output is correct
3 Correct 199 ms 2436 KB Output is correct
4 Correct 185 ms 2396 KB Output is correct
5 Correct 199 ms 2396 KB Output is correct
6 Correct 4806 ms 49896 KB Output is correct
7 Correct 4677 ms 49756 KB Output is correct
8 Correct 4663 ms 49772 KB Output is correct
9 Correct 4996 ms 50952 KB Output is correct
10 Correct 4978 ms 45816 KB Output is correct
11 Correct 4716 ms 45612 KB Output is correct
12 Correct 4647 ms 48460 KB Output is correct
13 Correct 4763 ms 45660 KB Output is correct
14 Correct 4585 ms 45648 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 11 ms 852 KB Output is correct
19 Correct 11 ms 604 KB Output is correct
20 Correct 11 ms 604 KB Output is correct
21 Correct 11 ms 604 KB Output is correct
22 Correct 11 ms 848 KB Output is correct
23 Correct 11 ms 856 KB Output is correct
24 Correct 12 ms 604 KB Output is correct
25 Correct 52 ms 3156 KB Output is correct
26 Correct 11 ms 604 KB Output is correct
27 Correct 420 ms 2296 KB Output is correct
28 Correct 4988 ms 57424 KB Output is correct
29 Correct 5309 ms 55088 KB Output is correct
30 Correct 5239 ms 55108 KB Output is correct
31 Correct 5270 ms 59216 KB Output is correct
32 Correct 4 ms 600 KB Output is correct

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 2436 KB Output is correct
2 Correct 160 ms 2392 KB Output is correct
3 Correct 188 ms 2392 KB Output is correct
4 Correct 191 ms 2396 KB Output is correct
5 Correct 177 ms 2396 KB Output is correct
6 Correct 4613 ms 49764 KB Output is correct
7 Correct 4524 ms 49756 KB Output is correct
8 Correct 4720 ms 49768 KB Output is correct
9 Correct 4911 ms 50964 KB Output is correct
10 Correct 4723 ms 45916 KB Output is correct
11 Correct 4707 ms 45824 KB Output is correct
12 Correct 4657 ms 48464 KB Output is correct
13 Correct 4696 ms 45816 KB Output is correct
14 Correct 4718 ms 45820 KB Output is correct
15 Runtime error 177 ms 125604 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -