oj.uz

Submission #678740

# Submission time Handle Problem Language Result Execution time Memory
678740 2023-01-06T13:07:31 Z jiahng Wombats (IOI13_wombats) C++14
55 / 100
 7678 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int R,C;
int H[5000][200], V[5000][200], ss[5000][200];
int tmp[200][200];
struct node{
    int s,e,m;
    int val[200][200];
    node *l,*r;
    bool leaf = 0;

    node(int _s,int _e){
        s = _s; e = _e; m = (s + e) / 2;

        if (e-s+1 > 2){
            l = new node(s,m); r = new node(m+1,e);
            merge();
        }else{
            leaf = 1;
            compleaf();
        }
    }
    void merge(){
        FOR(j,0,C-1) merge_one(0,C-1,0,C-1,j);
    }
    void merge_one(int a,int b,int vl,int vr, int j){
        if (a > b) return;
        int c = (a + b) / 2;

        int opt = -1;
        val[c][j] = INF;
        FOR(k,vl,vr){
            int res = l->val[c][k] + r->val[k][j] + V[m][k];
            if (res < val[c][j]){
                opt = k; val[c][j] = res;
            }
        }
        merge_one(a,c-1,vl,opt,j);
        merge_one(c+1,b,opt,vr,j);
    }

    void updV(int row){
        if (leaf){
            compleaf(); return;
        }
        if (m < row) r->updV(row);
        else if (m > row) l->updV(row);

        merge();
    }
    void compleaf(){
        FOR(i,0,C-1) FOR(j,0,C-1) val[i][j] = abs(ss[e][i] - ss[e][j]);
        DEC(l,e-1,s){
            FOR(i,0,C-1) FOR(j,0,C-1){
                tmp[i][j] = INF;
                FOR(k,0,C-1){
                    tmp[i][j] = min(tmp[i][j],
                            val[k][j] + abs(ss[l][k] - ss[l][i]) + V[l][k]);
                }
            }
            FOR(i,0,C-1) FOR(j,0,C-1) val[i][j] = tmp[i][j];
        }
    }

    void updH(int row){
        if (leaf){
            compleaf();
            return;
        }
        if (row > m) r->updH(row);
        else l->updH(row);
        merge();
    }
}*root;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    ::R = R; ::C = C;
    FOR(i,0,R-1) FOR(j,0,C-1){
        ::H[i][j] = H[i][j];
        ::V[i][j] = V[i][j];
    }
    FOR(i,0,R-1){
        ss[i][0] = 0;
        
        FOR(j,1,C-1){
            ss[i][j] = ss[i][j-1] + H[i][j-1];
        }
    }
    root = new node(0,R-1);

    /*
    FOR(i,0,C-1){
        FOR(j,0,C-1) cout << root->val[i][j] << ' ';
        cout << '\n';
    }
    */
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W; 
    FOR(j,1,C-1) ss[P][j] = ss[P][j-1] + H[P][j-1];

    root->updH(P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    root->updV(P);
}

int escape(int V1, int V2) {
    return root->val[V1][V2];
}

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 29 ms 64972 KB Output is correct
2 Correct 28 ms 65012 KB Output is correct
3 Correct 95 ms 66608 KB Output is correct
4 Correct 29 ms 65028 KB Output is correct
5 Correct 30 ms 64972 KB Output is correct
6 Correct 1 ms 268 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 912 KB Output is correct
11 Correct 65 ms 1776 KB Output is correct
12 Correct 1 ms 852 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 11500 KB Output is correct
2 Correct 212 ms 11504 KB Output is correct
3 Correct 306 ms 11468 KB Output is correct
4 Correct 253 ms 11556 KB Output is correct
5 Correct 271 ms 11420 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1032 ms 11508 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 68924 KB Output is correct
2 Correct 38 ms 68928 KB Output is correct
3 Correct 38 ms 68936 KB Output is correct
4 Correct 68 ms 69672 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 11508 KB Output is correct
2 Correct 225 ms 11468 KB Output is correct
3 Correct 307 ms 11508 KB Output is correct
4 Correct 291 ms 11596 KB Output is correct
5 Correct 274 ms 11596 KB Output is correct
6 Correct 37 ms 68820 KB Output is correct
7 Correct 33 ms 68916 KB Output is correct
8 Correct 40 ms 68824 KB Output is correct
9 Correct 74 ms 69752 KB Output is correct
10 Correct 32 ms 64988 KB Output is correct
11 Correct 32 ms 64960 KB Output is correct
12 Correct 92 ms 66572 KB Output is correct
13 Correct 34 ms 64972 KB Output is correct
14 Correct 34 ms 64972 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 1 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 64 ms 1864 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 1082 ms 11504 KB Output is correct
28 Runtime error 1969 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 11500 KB Output is correct
2 Correct 219 ms 11504 KB Output is correct
3 Correct 316 ms 11504 KB Output is correct
4 Correct 263 ms 11508 KB Output is correct
5 Correct 300 ms 11620 KB Output is correct
6 Correct 40 ms 68848 KB Output is correct
7 Correct 39 ms 68892 KB Output is correct
8 Correct 34 ms 68924 KB Output is correct
9 Correct 64 ms 69708 KB Output is correct
10 Correct 29 ms 65032 KB Output is correct
11 Correct 28 ms 64944 KB Output is correct
12 Correct 90 ms 66600 KB Output is correct
13 Correct 29 ms 64980 KB Output is correct
14 Correct 37 ms 64968 KB Output is correct
15 Runtime error 7678 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -