oj.uz

Submission #1035684

# Submission time Handle Problem Language Result Execution time Memory
1035684 2024-07-26T13:37:16 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 = 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) {
    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);*/
    /*seg = SEGTREE(n);*/
    /*rep(u, n) seg.upd(u, a[u]);*/

    recalc();
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    recalc(); return;
    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;
    recalc(); return;
    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

# Verdict Execution time Memory Grader output
1 Correct 127 ms 25176 KB Output is correct
2 Correct 123 ms 25180 KB Output is correct
3 Correct 152 ms 27984 KB Output is correct
4 Correct 115 ms 25180 KB Output is correct
5 Correct 143 ms 25432 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 600 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory 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 604 KB Output is correct
5 Correct 1 ms 604 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 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 40 ms 1564 KB Output is correct
12 Correct 1 ms 600 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7955 ms 4628 KB Output is correct
2 Correct 6959 ms 4700 KB Output is correct
3 Correct 7592 ms 4696 KB Output is correct
4 Correct 7291 ms 4696 KB Output is correct
5 Correct 6935 ms 4696 KB Output is correct
6 Correct 0 ms 348 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 20088 ms 4768 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 31068 KB Output is correct
2 Correct 174 ms 31068 KB Output is correct
3 Correct 174 ms 31204 KB Output is correct
4 Correct 194 ms 32336 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7188 ms 4708 KB Output is correct
2 Correct 6922 ms 4696 KB Output is correct
3 Correct 7506 ms 4696 KB Output is correct
4 Correct 7234 ms 4952 KB Output is correct
5 Correct 7092 ms 4696 KB Output is correct
6 Correct 192 ms 31068 KB Output is correct
7 Correct 178 ms 31068 KB Output is correct
8 Correct 184 ms 31200 KB Output is correct
9 Correct 212 ms 32340 KB Output is correct
10 Correct 107 ms 25176 KB Output is correct
11 Correct 127 ms 25180 KB Output is correct
12 Correct 148 ms 27984 KB Output is correct
13 Correct 115 ms 25180 KB Output is correct
14 Correct 107 ms 25180 KB Output is correct
15 Correct 0 ms 344 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 600 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 748 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 38 ms 2928 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Execution timed out 20004 ms 4748 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7883 ms 4704 KB Output is correct
2 Correct 6441 ms 4700 KB Output is correct
3 Correct 7504 ms 4748 KB Output is correct
4 Correct 7439 ms 4952 KB Output is correct
5 Correct 7289 ms 4696 KB Output is correct
6 Correct 189 ms 31068 KB Output is correct
7 Correct 167 ms 31068 KB Output is correct
8 Correct 167 ms 31064 KB Output is correct
9 Correct 200 ms 32336 KB Output is correct
10 Correct 131 ms 25180 KB Output is correct
11 Correct 110 ms 25176 KB Output is correct
12 Correct 144 ms 27984 KB Output is correct
13 Correct 116 ms 25176 KB Output is correct
14 Correct 117 ms 25176 KB Output is correct
15 Runtime error 366 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -