oj.uz

Submission #289038

# Submission time Handle Problem Language Result Execution time Memory
289038 2020-09-02T09:52:50 Z egekabas Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 262148 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 = 50;
int h[5000][200];
int v[5000][200];
int dis[5000/sq+5][200][sq+5][200];
void dijkstra(int beg, int end, int imp, int dis[5000][200]){
    for(int i = beg; i <= end; ++i)
        for(int j = 0; j < c; ++j)
            dis[i-beg][j] = 1e9+7;
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
    dis[end-beg][imp] = 0;
    pq.push({0, {end, imp}});

    while(pq.size()){
        int d = pq.top().ff;
        int x = pq.top().ss.ff;
        int y = pq.top().ss.ss;
        pq.pop();
        if(d > dis[x-beg][y])
            continue;
        if(x > beg && dis[x-1-beg][y] > d + v[x-1][y]){
            dis[x-1-beg][y] = d + v[x-1][y];
            pq.push({dis[x-1-beg][y], {x-1, y}});
        }
        if(y > 0 && dis[x-beg][y-1] > d + h[x][y-1]){
            dis[x-beg][y-1] = d + h[x][y-1];
            pq.push({dis[x-beg][y-1], {x, y-1}});
        }
        if(y < c-1 && dis[x-beg][y+1] > d + h[x][y]){
            dis[x-beg][y+1] = d + h[x][y];
            pq.push({dis[x-beg][y+1], {x, y+1}});
        }
    }
}

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]);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    int gr = P/sq;
    for(int j = 0; j < c; ++j)
        dijkstra(gr*sq, min(r-1, (gr+1)*sq), j, dis[gr][j]);
    if(gr > 0 && P%sq == 0){
        --gr;
        for(int j = 0; j < c; ++j)
            dijkstra(gr*sq, min(r-1, (gr+1)*sq), j, dis[gr][j]);
    }
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    int gr = P/sq;
    for(int j = 0; j < c; ++j)
        dijkstra(gr*sq, min(r-1, (gr+1)*sq), j, dis[gr][j]);
}

int escape(int V1, int V2) {
    vector<int> curd(c, 1e9+7);
    vector<int> newd(c, 1e9+7);
    curd[V1] = 0;
    for(int i = 0; i < r; i += sq){
        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][0][j]);
        for(int j = 0; j < c; ++j){
            curd[j] = newd[j];
            newd[j] = 1e9+7;
        }
    }
    assert(curd[V2] >= 0);
    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 12 ms 16768 KB Output is correct
2 Correct 13 ms 16768 KB Output is correct
3 Correct 251 ms 18316 KB Output is correct
4 Correct 12 ms 16768 KB Output is correct
5 Correct 12 ms 16768 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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7131 ms 9216 KB Output is correct
2 Correct 12066 ms 9208 KB Output is correct
3 Correct 7333 ms 9464 KB Output is correct
4 Correct 7322 ms 9380 KB Output is correct
5 Correct 7274 ms 9428 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 Execution timed out 20047 ms 9336 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24960 KB Output is correct
2 Correct 29 ms 25088 KB Output is correct
3 Correct 25 ms 24960 KB Output is correct
4 Correct 211 ms 25848 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6988 ms 9212 KB Output is correct
2 Correct 11983 ms 9200 KB Output is correct
3 Correct 7465 ms 9388 KB Output is correct
4 Correct 7291 ms 9464 KB Output is correct
5 Correct 7171 ms 9288 KB Output is correct
6 Correct 24 ms 25088 KB Output is correct
7 Correct 28 ms 25088 KB Output is correct
8 Correct 25 ms 25088 KB Output is correct
9 Correct 202 ms 26436 KB Output is correct
10 Correct 12 ms 16768 KB Output is correct
11 Correct 12 ms 16768 KB Output is correct
12 Correct 254 ms 19704 KB Output is correct
13 Correct 12 ms 16768 KB Output is correct
14 Correct 12 ms 16768 KB Output is correct
15 Correct 0 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 2 ms 768 KB Output is correct
19 Correct 2 ms 768 KB Output is correct
20 Correct 2 ms 768 KB Output is correct
21 Correct 2 ms 768 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 768 KB Output is correct
24 Correct 2 ms 768 KB Output is correct
25 Correct 206 ms 3192 KB Output is correct
26 Correct 3 ms 768 KB Output is correct
27 Execution timed out 20095 ms 9464 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6975 ms 9324 KB Output is correct
2 Correct 12026 ms 9212 KB Output is correct
3 Correct 7252 ms 9380 KB Output is correct
4 Correct 7235 ms 9464 KB Output is correct
5 Correct 7199 ms 9336 KB Output is correct
6 Correct 24 ms 25088 KB Output is correct
7 Correct 28 ms 25088 KB Output is correct
8 Correct 25 ms 25088 KB Output is correct
9 Correct 207 ms 26488 KB Output is correct
10 Correct 11 ms 16768 KB Output is correct
11 Correct 12 ms 16768 KB Output is correct
12 Correct 255 ms 19576 KB Output is correct
13 Correct 12 ms 16768 KB Output is correct
14 Correct 12 ms 16768 KB Output is correct
15 Runtime error 5716 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -