oj.uz

Submission #678733

# Submission time Handle Problem Language Result Execution time Memory
678733 2023-01-06T13:03:48 Z jiahng Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 67096 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 > 20){
            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 10 ms 20180 KB Output is correct
2 Correct 10 ms 20180 KB Output is correct
3 Correct 75 ms 21804 KB Output is correct
4 Correct 10 ms 20180 KB Output is correct
5 Correct 10 ms 20180 KB Output is correct
6 Correct 1 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 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 1 ms 460 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 64 ms 1352 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 2056 KB Output is correct
2 Correct 1738 ms 2020 KB Output is correct
3 Correct 1893 ms 2180 KB Output is correct
4 Correct 1830 ms 2068 KB Output is correct
5 Correct 1805 ms 2064 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
9 Correct 8790 ms 2064 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24032 KB Output is correct
2 Correct 13 ms 24076 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 47 ms 24916 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1837 ms 2060 KB Output is correct
2 Correct 1850 ms 2060 KB Output is correct
3 Correct 2072 ms 2060 KB Output is correct
4 Correct 1896 ms 2064 KB Output is correct
5 Correct 1970 ms 2064 KB Output is correct
6 Correct 13 ms 24004 KB Output is correct
7 Correct 13 ms 24128 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 44 ms 24912 KB Output is correct
10 Correct 14 ms 20208 KB Output is correct
11 Correct 10 ms 20228 KB Output is correct
12 Correct 92 ms 21768 KB Output is correct
13 Correct 13 ms 20180 KB Output is correct
14 Correct 12 ms 20188 KB Output is correct
15 Correct 0 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 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 372 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 63 ms 1340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 8765 ms 2072 KB Output is correct
28 Execution timed out 20089 ms 67096 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 2064 KB Output is correct
2 Correct 1742 ms 2064 KB Output is correct
3 Correct 1935 ms 2184 KB Output is correct
4 Correct 1843 ms 1996 KB Output is correct
5 Correct 1822 ms 2144 KB Output is correct
6 Correct 12 ms 24020 KB Output is correct
7 Correct 12 ms 24020 KB Output is correct
8 Correct 13 ms 24140 KB Output is correct
9 Correct 47 ms 24920 KB Output is correct
10 Correct 13 ms 20148 KB Output is correct
11 Correct 10 ms 20204 KB Output is correct
12 Correct 75 ms 21768 KB Output is correct
13 Correct 10 ms 20180 KB Output is correct
14 Correct 11 ms 20180 KB Output is correct
15 Execution timed out 20046 ms 58324 KB Time limit exceeded
16 Halted 0 ms 0 KB -