oj.uz

답안 #1035690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035690 2024-07-26T13:41:14 Z c2zi6 웜뱃 (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 = 100;

int n, m;
struct PART {
    int d[MAXC][MAXC];
    PART() {
        clear();
    }
    void clear() {
        rep(i, m) rep(j, m) d[i][j] = 1e9;
    }
    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 set(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]);
        }
        rep(u, m) rep(v, m) d[u][v] = c.d[u][v];
    }
    void print() {
        rep(i, m) {
            rep(j, m) cout << d[i][j] << " ";
            cout << endl;
        }
    }
};

vector<PART> a;
PART answer;
VVI H, V;

struct SEGTREE {
    int n;
    vector<PART> tree;
    SEGTREE(){}
    SEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = vector<PART>(2*n);
        rep(u, 2*n) {
            /*rep(i, n) rep(j, m) {*/
            rep(i, n) tree[u].d[i][i] = 0;
            /*tree[u].d[0][0] = -1;*/
        }
    }
    void upd(int N, int L, int R, int i, const PART& nw) {
        if (i < L || i > R) return;
        if (L == R) {
            tree[N] = nw;
            return;
        }
        int M = (L + R) / 2;
        upd(2*N+1, L, M, i, nw);
        upd(2*N+2, M+1, R, i, nw);
        tree[N].set(tree[2*N+1], tree[2*N+2]);
    }
    void upd(int i, const PART& nw) {
        upd(0, 0, n-1, i, nw);
    }
    void print() {
        rep(u, 2*n-1) {
            cout << u << ": " << endl;
            tree[u].print();
        }
    }
} seg;

void recalcpart(int ind) {
    a[ind].clear();
    replr(i, 0, m-1) {
        int sum = 0;
        replr(j, i, m-1) {
            a[ind].d[i][j] = sum + V[ind][j];
            a[ind].d[j][i] = sum + V[ind][i];
            sum += H[ind][j];
        }
    }
}

void recalc() {
    rep(u, n) a[u].clear();
    rep(u, n) {
        recalcpart(u);
    }
    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];
    a = vector<PART>(n);

    rep(i, n) recalcpart(i);
    answer = a[0];
    replr(i, 1, n-1) answer.add(a[i]);


    /*seg = SEGTREE(n);*/
    /*rep(u, n) seg.upd(u, a[u]);*/

    /*recalc();*/
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    recalcpart(P);
    /*seg.upd(P, a[P]);*/

    answer = a[0];
    replr(i, 1, n-1) answer.add(a[i]);

    /*cout << "------------------------------------" << endl;*/
    /*seg.tree[0].print();*/
    /*cout << "------------------------------------" << endl;*/
    /*answer.print();*/
    /*cout << "------------------------------------" << endl;*/
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    recalcpart(P);
    /*seg.upd(P, a[P]);*/

    answer = a[0];
    replr(i, 1, n-1) answer.add(a[i]);

    /*cout << "------------------------------------" << endl;*/
    /*seg.tree[0].print();*/
    /*cout << "------------------------------------" << endl;*/
    /*answer.print();*/
    /*cout << "------------------------------------" << endl;*/
}

int escape(int u, int v) {
    /*return seg.tree[0].d[u][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

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 25176 KB Output is correct
2 Correct 90 ms 25176 KB Output is correct
3 Correct 124 ms 26888 KB Output is correct
4 Correct 100 ms 25172 KB Output is correct
5 Correct 85 ms 25176 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 38 ms 1672 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7663 ms 4628 KB Output is correct
2 Correct 6868 ms 4700 KB Output is correct
3 Correct 8096 ms 4952 KB Output is correct
4 Correct 7952 ms 4700 KB Output is correct
5 Correct 7550 ms 4552 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 20092 ms 4700 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 31192 KB Output is correct
2 Correct 120 ms 31068 KB Output is correct
3 Correct 136 ms 31092 KB Output is correct
4 Correct 156 ms 32340 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7613 ms 4700 KB Output is correct
2 Correct 6921 ms 4700 KB Output is correct
3 Correct 8210 ms 4672 KB Output is correct
4 Correct 7845 ms 4696 KB Output is correct
5 Correct 7706 ms 4700 KB Output is correct
6 Correct 138 ms 31140 KB Output is correct
7 Correct 118 ms 31068 KB Output is correct
8 Correct 139 ms 31064 KB Output is correct
9 Correct 166 ms 32336 KB Output is correct
10 Correct 76 ms 25176 KB Output is correct
11 Correct 78 ms 25180 KB Output is correct
12 Correct 121 ms 27984 KB Output is correct
13 Correct 86 ms 25180 KB Output is correct
14 Correct 113 ms 25180 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 41 ms 3004 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Execution timed out 20091 ms 4740 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7112 ms 4700 KB Output is correct
2 Correct 6304 ms 4696 KB Output is correct
3 Correct 7085 ms 4696 KB Output is correct
4 Correct 7382 ms 4444 KB Output is correct
5 Correct 7488 ms 4696 KB Output is correct
6 Correct 161 ms 31064 KB Output is correct
7 Correct 125 ms 31068 KB Output is correct
8 Correct 155 ms 31064 KB Output is correct
9 Correct 170 ms 32384 KB Output is correct
10 Correct 94 ms 25180 KB Output is correct
11 Correct 91 ms 25176 KB Output is correct
12 Correct 139 ms 28020 KB Output is correct
13 Correct 90 ms 25180 KB Output is correct
14 Correct 89 ms 25176 KB Output is correct
15 Runtime error 2202 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -