oj.uz

Submission #756866

# Submission time Handle Problem Language Result Execution time Memory
756866 2023-06-12T10:43:02 Z DJeniUp Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 81880 KB 
#include "wombats.h"
#include "bits/stdc++.h"

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define fr first
#define sc second
#define A 16
#define INF 1000000007

ll h[5007][207],v[5007][207],n,m,f[207],res[207][207],g[5007][207],l[2][207];

ll d[5007/A+1][207][207];

priority_queue<pairll, vector<pairll>, greater<pairll> >q;

void S(ll x){
    //cout<<x<<endl;
    ll y=x;
    y*=A;
    for(int k=0;k<m;k++){
        for(int i=y;i<=y+A;i++){
            for(int j=0;j<m;j++){
                g[i][j]=INF;
            }
        }
        g[y][k]=0;
        q.push({0,y*m+k});
        while(q.size()>0){
            ll m1=q.top().fr;
            ll x1=q.top().sc/m;
            ll y1=q.top().sc%m;
            q.pop();
            if(x1<min(n-1,y+A)){
                if(g[x1+1][y1]>m1+v[x1][y1]){
                    g[x1+1][y1]=m1+v[x1][y1];
                    q.push({m1+v[x1][y1],m*(x1+1)+y1});
                }
            }
            if(y1>0){
                if(g[x1][y1-1]>m1+h[x1][y1-1]){
                    g[x1][y1-1]=m1+h[x1][y1-1];
                    q.push({m1+h[x1][y1-1],x1*m+y1-1});
                }
            }
            if(y1<m-1){
                if(g[x1][y1+1]>m1+h[x1][y1]){
                    g[x1][y1+1]=m1+h[x1][y1];
                    q.push({m1+h[x1][y1],x1*m+y1+1});
                }
            }
        }
        for(int j=0;j<m;j++){
            d[x][k][j]=g[min(n-1,y+A)][j];
        }
    }
    
    return ;
}

void R(ll x){
    f[x]=1;
    for(int i=0;i<m;i++){
        l[0][i]=INF;
    }
    l[0][x]=0;
    for(int i=0;i<=(n-1)/A;i++){
        for(int j=0;j<m;j++){
            l[1][j]=INF;
            for(int k=0;k<m;k++){
                l[1][j]=min(l[1][j],l[0][k]+d[i][k][j]);
            }
        }
        swap(l[0],l[1]);
    }
    for(int i=0;i<m;i++){
        res[x][i]=l[0][i];
    }
    return ;
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n=R;
    m=C;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            h[i][j]=H[i][j];
            v[i][j]=V[i][j];
        }
    }
    for(int i=0;i<=(n-1)/A;i++){
        S(i);
    }
    return ;
}

void changeH(int x, int y, int val) {
    h[x][y]=val;
    for(int i=0;i<m;i++){
        f[i]=0;
    }
    if(x%A==0){
        if(x!=0)S(x/A-1);
    }
    S(x/A);
    return ;
}

void changeV(int x, int y, int val) {
    for(int i=0;i<m;i++){
        f[i]=0;
    }
    v[x][y]=val;
    S(x/A);
    return ;
}

int escape(int y1, int y2) {
    if(f[y1]==0){
        R(y1);
    }
    return res[y1][y2];
}

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 18 ms 17776 KB Output is correct
2 Correct 21 ms 17748 KB Output is correct
3 Correct 84 ms 20556 KB Output is correct
4 Correct 19 ms 17748 KB Output is correct
5 Correct 19 ms 17736 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 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 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 72 ms 2796 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1429 ms 1772 KB Output is correct
2 Correct 2819 ms 1648 KB Output is correct
3 Correct 1499 ms 1600 KB Output is correct
4 Correct 1405 ms 1592 KB Output is correct
5 Correct 1534 ms 1544 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 12592 ms 1452 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 47 ms 21964 KB Output is correct
2 Correct 45 ms 21948 KB Output is correct
3 Correct 34 ms 21972 KB Output is correct
4 Correct 76 ms 23312 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1369 ms 1488 KB Output is correct
2 Correct 2879 ms 1728 KB Output is correct
3 Correct 1508 ms 1620 KB Output is correct
4 Correct 1396 ms 1588 KB Output is correct
5 Correct 1548 ms 1716 KB Output is correct
6 Correct 35 ms 21972 KB Output is correct
7 Correct 35 ms 21936 KB Output is correct
8 Correct 42 ms 21932 KB Output is correct
9 Correct 87 ms 23256 KB Output is correct
10 Correct 20 ms 17780 KB Output is correct
11 Correct 18 ms 17748 KB Output is correct
12 Correct 85 ms 20552 KB Output is correct
13 Correct 19 ms 17792 KB Output is correct
14 Correct 19 ms 17756 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 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 2 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 2 ms 440 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 72 ms 2828 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 12617 ms 1448 KB Output is correct
28 Execution timed out 20019 ms 50624 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 1600 KB Output is correct
2 Correct 2722 ms 1608 KB Output is correct
3 Correct 1411 ms 1620 KB Output is correct
4 Correct 1394 ms 1552 KB Output is correct
5 Correct 1614 ms 1556 KB Output is correct
6 Correct 52 ms 21912 KB Output is correct
7 Correct 36 ms 21960 KB Output is correct
8 Correct 38 ms 21972 KB Output is correct
9 Correct 95 ms 23244 KB Output is correct
10 Correct 20 ms 17748 KB Output is correct
11 Correct 19 ms 17768 KB Output is correct
12 Correct 97 ms 20496 KB Output is correct
13 Correct 20 ms 17740 KB Output is correct
14 Correct 27 ms 17748 KB Output is correct
15 Correct 9917 ms 81880 KB Output is correct
16 Execution timed out 20026 ms 80420 KB Time limit exceeded
17 Halted 0 ms 0 KB -