oj.uz

Submission #289092

# Submission time Handle Problem Language Result Execution time Memory
289092 2020-09-02T10:44:30 Z egekabas Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 16888 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int r, c;
const int sq = 10001;
int h[5000][200];
int v[5000][200];
int dis[5000/sq+5][200][200];
void dijkstra(int beg, int end, int imp, int dis[200]){
    for(int j = 0; j < c; ++j)
        dis[j] = 1e9+7;
    dis[imp] = 0;
    for(int i = end; i >= beg; --i){
        for(int j = 1; j < c; ++j)
            dis[j] = min(dis[j], dis[j-1]+h[i][j-1]);
        for(int j = c-2; j >= 0; --j)
            dis[j] = min(dis[j], dis[j+1]+h[i][j]);
        for(int j = 0; j < c && i != beg; ++j)
            dis[j] = min((int)1e9+7, dis[j] + v[i-1][j]);
    }
}
    
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    for(int i = 0; i < r; ++i)
        for(int j = 0; j < c; ++j){
            h[i][j] = H[i][j];
            v[i][j] = V[i][j];
        }
    for(int i = 0; i < r; i += sq)
        for(int j = 0; j < c; ++j)
            dijkstra(i, min(i+sq, r-1), j, dis[i/sq][j]);
}
vector<int> change;
void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    int gr = P/sq;
    change.pb(gr);
    if(gr > 0 && P%sq == 0){
        change.pb(gr-1);
    }
}
    
void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    int gr = P/sq;
    change.pb(gr);
}
int curd[200];
int newd[200];
int done[5000/sq+5];
int escape(int V1, int V2) {
    for(auto u : change){
        if(done[u]) continue;
        for(int j = 0; j < c; ++j)
            dijkstra(u*sq, min(r-1, (u+1)*sq), j, dis[u][j]);
    }
    for(auto u : change)
        done[u] = 0;
    change.clear();
    for(int j = 0; j < c; ++j)
        curd[j] = newd[j] = 1e9+7;
    curd[V1] = 0;
    for(int i = 0; i < r; i += sq){
        if(i + sq >= r){
            for(int j = 0; j < c; ++j){
                newd[V2] = min(newd[V2], curd[j]+dis[i/sq][V2][j]);
            }   
            return newd[V2]; 
        }
        for(int j = 0; j < c; ++j)
            for(int k = 0; k < c; ++k)
                newd[k] = min(newd[k], curd[j]+dis[i/sq][k][j]);
        for(int j = 0; j < c; ++j){
            curd[j] = newd[j];
            newd[j] = 1e9+7;
        }
    }
    return curd[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 19 ms 12032 KB Output is correct
2 Correct 19 ms 12032 KB Output is correct
3 Correct 103 ms 13688 KB Output is correct
4 Correct 19 ms 12032 KB Output is correct
5 Correct 19 ms 12032 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 97 ms 1400 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 904 KB Output is correct
2 Correct 938 ms 888 KB Output is correct
3 Correct 961 ms 896 KB Output is correct
4 Correct 986 ms 768 KB Output is correct
5 Correct 959 ms 888 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4623 ms 800 KB Output is correct
10 Correct 0 ms 416 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 16024 KB Output is correct
2 Correct 77 ms 15984 KB Output is correct
3 Correct 75 ms 16000 KB Output is correct
4 Correct 133 ms 16760 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 768 KB Output is correct
2 Correct 942 ms 888 KB Output is correct
3 Correct 963 ms 892 KB Output is correct
4 Correct 972 ms 888 KB Output is correct
5 Correct 927 ms 888 KB Output is correct
6 Correct 76 ms 16000 KB Output is correct
7 Correct 77 ms 16000 KB Output is correct
8 Correct 78 ms 16000 KB Output is correct
9 Correct 120 ms 16760 KB Output is correct
10 Correct 19 ms 12032 KB Output is correct
11 Correct 19 ms 12032 KB Output is correct
12 Correct 103 ms 13692 KB Output is correct
13 Correct 20 ms 12160 KB Output is correct
14 Correct 19 ms 12032 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 97 ms 1400 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 4604 ms 792 KB Output is correct
28 Execution timed out 20076 ms 16180 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 776 KB Output is correct
2 Correct 935 ms 768 KB Output is correct
3 Correct 975 ms 792 KB Output is correct
4 Correct 973 ms 892 KB Output is correct
5 Correct 931 ms 888 KB Output is correct
6 Correct 76 ms 16000 KB Output is correct
7 Correct 78 ms 16000 KB Output is correct
8 Correct 77 ms 16000 KB Output is correct
9 Correct 119 ms 16888 KB Output is correct
10 Correct 19 ms 12032 KB Output is correct
11 Correct 19 ms 12032 KB Output is correct
12 Correct 107 ms 13820 KB Output is correct
13 Correct 19 ms 12032 KB Output is correct
14 Correct 19 ms 12032 KB Output is correct
15 Correct 10692 ms 16308 KB Output is correct
16 Execution timed out 20086 ms 16424 KB Time limit exceeded
17 Halted 0 ms 0 KB -