oj.uz

Submission #678748

# Submission time Handle Problem Language Result Execution time Memory
678748 2023-01-06T13:12:08 Z jiahng Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 198400 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 >8){
            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 15 ms 32980 KB Output is correct
2 Correct 17 ms 32956 KB Output is correct
3 Correct 79 ms 34524 KB Output is correct
4 Correct 18 ms 32880 KB Output is correct
5 Correct 16 ms 32980 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 3408 KB Output is correct
2 Correct 898 ms 3428 KB Output is correct
3 Correct 1093 ms 3532 KB Output is correct
4 Correct 913 ms 3452 KB Output is correct
5 Correct 950 ms 3416 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 4353 ms 3420 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 21 ms 36820 KB Output is correct
2 Correct 20 ms 36856 KB Output is correct
3 Correct 18 ms 36820 KB Output is correct
4 Correct 53 ms 37568 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 3404 KB Output is correct
2 Correct 868 ms 3404 KB Output is correct
3 Correct 1008 ms 3532 KB Output is correct
4 Correct 956 ms 3468 KB Output is correct
5 Correct 956 ms 3408 KB Output is correct
6 Correct 17 ms 36820 KB Output is correct
7 Correct 20 ms 36784 KB Output is correct
8 Correct 21 ms 36864 KB Output is correct
9 Correct 60 ms 37584 KB Output is correct
10 Correct 17 ms 32936 KB Output is correct
11 Correct 16 ms 32980 KB Output is correct
12 Correct 82 ms 34516 KB Output is correct
13 Correct 16 ms 32980 KB Output is correct
14 Correct 15 ms 32980 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 64 ms 1512 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 4405 ms 3408 KB Output is correct
28 Correct 9871 ms 192872 KB Output is correct
29 Correct 11420 ms 106572 KB Output is correct
30 Correct 11660 ms 106740 KB Output is correct
31 Correct 10037 ms 198400 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 921 ms 3540 KB Output is correct
2 Correct 883 ms 3436 KB Output is correct
3 Correct 1046 ms 3612 KB Output is correct
4 Correct 919 ms 3412 KB Output is correct
5 Correct 940 ms 3456 KB Output is correct
6 Correct 19 ms 36820 KB Output is correct
7 Correct 23 ms 36884 KB Output is correct
8 Correct 20 ms 36908 KB Output is correct
9 Correct 54 ms 37672 KB Output is correct
10 Correct 16 ms 32980 KB Output is correct
11 Correct 17 ms 32968 KB Output is correct
12 Correct 84 ms 34672 KB Output is correct
13 Correct 16 ms 32900 KB Output is correct
14 Correct 16 ms 32928 KB Output is correct
15 Execution timed out 20025 ms 155744 KB Time limit exceeded
16 Halted 0 ms 0 KB -