oj.uz

Submission #1035688

# Submission time Handle Problem Language Result Execution time Memory
1035688 2024-07-26T13:40:14 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(u, n) a[u].clear();
    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;
    a[P].clear();
    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;
    a[P].clear();
    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 86 ms 25180 KB Output is correct
2 Correct 99 ms 25352 KB Output is correct
3 Correct 131 ms 26904 KB Output is correct
4 Correct 89 ms 25180 KB Output is correct
5 Correct 87 ms 25180 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 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 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 38 ms 1540 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 7453 ms 4444 KB Output is correct
2 Correct 6502 ms 4628 KB Output is correct
3 Correct 7342 ms 4440 KB Output is correct
4 Correct 7538 ms 4440 KB Output is correct
5 Correct 6773 ms 4444 KB Output is correct
6 Correct 1 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 4676 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 31124 KB Output is correct
2 Correct 146 ms 31064 KB Output is correct
3 Correct 142 ms 31068 KB Output is correct
4 Correct 184 ms 31912 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8198 ms 4624 KB Output is correct
2 Correct 6859 ms 4440 KB Output is correct
3 Correct 7741 ms 4696 KB Output is correct
4 Correct 7948 ms 4748 KB Output is correct
5 Correct 7897 ms 4700 KB Output is correct
6 Correct 147 ms 31064 KB Output is correct
7 Correct 122 ms 31064 KB Output is correct
8 Correct 142 ms 31064 KB Output is correct
9 Correct 159 ms 32336 KB Output is correct
10 Correct 82 ms 25180 KB Output is correct
11 Correct 86 ms 25180 KB Output is correct
12 Correct 114 ms 27984 KB Output is correct
13 Correct 89 ms 25180 KB Output is correct
14 Correct 88 ms 25176 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 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 600 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 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 40 ms 3000 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Execution timed out 20046 ms 4696 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7486 ms 4696 KB Output is correct
2 Correct 6934 ms 4700 KB Output is correct
3 Correct 8047 ms 4700 KB Output is correct
4 Correct 7968 ms 4700 KB Output is correct
5 Correct 7690 ms 4740 KB Output is correct
6 Correct 172 ms 31068 KB Output is correct
7 Correct 125 ms 31064 KB Output is correct
8 Correct 143 ms 31068 KB Output is correct
9 Correct 165 ms 32340 KB Output is correct
10 Correct 89 ms 25180 KB Output is correct
11 Correct 91 ms 25176 KB Output is correct
12 Correct 121 ms 28028 KB Output is correct
13 Correct 103 ms 25176 KB Output is correct
14 Correct 93 ms 25180 KB Output is correct
15 Runtime error 2569 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -