oj.uz

Submission #1035718

# Submission time Handle Problem Language Result Execution time Memory
1035718 2024-07-26T14:08:43 Z c2zi6 Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 108372 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "wombats.h"
 
const int MAXC = 200;
 
int n, m;
struct PART {
    int d[MAXC][MAXC];
    PART() {
        rep(i, m) rep(j, m) d[i][j] = 2e9;
    }
    void add(const PART& b) {
        PART c;
        rep(u, m) rep(v, m) rep(mid, m) {
            setmin(c.d[u][v], d[u][mid] + b.d[mid][v]);
        }
        rep(u, m) rep(v, m) d[u][v] = c.d[u][v];
    }
};
void combine(const PART& a, const PART& b) {
    PART c;
    rep(u, m) rep(v, m) rep(mid, m) {
        setmin(c.d[u][v], a.d[u][mid] + b.d[mid][v]);
    }
}
vector<PART> a;
PART answer;
VVI H, V;
 
void recalc() {
    a = vector<PART>(n);
    rep(u, n) {
        replr(i, 0, m-1) {
            int sum = 0;
            replr(j, i, m-1) {
                a[u].d[i][j] = sum + V[u][j];
                a[u].d[j][i] = sum + V[u][i];
                sum += H[u][j];
            }
        }
    }
    answer = a[0];
    replr(i, 1, n-1) answer.add(a[i]);
}
 
bool lucum1;

void init(int R, int C, int H_arg[5000][200], int V_arg[5000][200]) {
    lucum1 = (C <= 20);
    n = R;
    m = C;
 
    H = V = VVI(n, VI(m));
    rep(i, n) rep(j, m-1) H[i][j] = H_arg[i][j];
    rep(i, n-1) rep(j, m) V[i][j] = V_arg[i][j];
 
    if (lucum1) recalc();
}
 
void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    if (lucum1) recalc();
    /* ... */
}
 
void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    if (lucum1) recalc();
    /* ... */
}
 
int escape(int U1, int U2) {
    if (lucum1) return answer.d[U1][U2];

    int sz = (n+1) * (m+1);
    VVPI gp(sz);
    rep(i, n) rep(j, m) {
        if (j+1 < m) {
            gp[i*m+j].pb({i*m+(j+1), H[i][j]});
            gp[i*m+(j+1)].pb({i*m+j, H[i][j]});
        }
        gp[i*m+j].pb({(i+1)*m+j, V[i][j]});
    }

    VI dist(sz, 1e9);
    VI vis(sz);
    priority_queue<PII> pq;
    pq.push({0, 0*m+U1});
    dist[0*m+U1] = 0;
    while (pq.size()) {
        int u = pq.top().ss;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto[v, w] : gp[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    return dist[n*m+U2];
}

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;
      |      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:125:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |         for (auto[v, w] : gp[u]) {
      |                  ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4209 ms 57308 KB Output is correct
2 Correct 4359 ms 55904 KB Output is correct
3 Correct 4312 ms 57536 KB Output is correct
4 Correct 4286 ms 57108 KB Output is correct
5 Correct 4526 ms 55892 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 40 ms 3440 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 1384 KB Output is correct
2 Correct 218 ms 1648 KB Output is correct
3 Correct 167 ms 1388 KB Output is correct
4 Correct 169 ms 1388 KB Output is correct
5 Correct 163 ms 1388 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 212 ms 1388 KB Output is correct
10 Correct 1 ms 600 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5015 ms 67360 KB Output is correct
2 Correct 4844 ms 67332 KB Output is correct
3 Correct 5051 ms 67484 KB Output is correct
4 Correct 5012 ms 67580 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 1388 KB Output is correct
2 Correct 227 ms 1644 KB Output is correct
3 Correct 175 ms 1388 KB Output is correct
4 Correct 171 ms 1608 KB Output is correct
5 Correct 181 ms 1388 KB Output is correct
6 Correct 5056 ms 65824 KB Output is correct
7 Correct 5341 ms 67340 KB Output is correct
8 Correct 5691 ms 67348 KB Output is correct
9 Correct 5233 ms 67740 KB Output is correct
10 Correct 4534 ms 57352 KB Output is correct
11 Correct 4402 ms 57340 KB Output is correct
12 Correct 4161 ms 55940 KB Output is correct
13 Correct 4318 ms 55892 KB Output is correct
14 Correct 4606 ms 55888 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 968 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 40 ms 3424 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct
27 Correct 230 ms 1596 KB Output is correct
28 Execution timed out 20093 ms 57180 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 1384 KB Output is correct
2 Correct 223 ms 1884 KB Output is correct
3 Correct 172 ms 1384 KB Output is correct
4 Correct 171 ms 1596 KB Output is correct
5 Correct 170 ms 1564 KB Output is correct
6 Correct 4740 ms 67248 KB Output is correct
7 Correct 5365 ms 67332 KB Output is correct
8 Correct 5566 ms 68720 KB Output is correct
9 Correct 5359 ms 69804 KB Output is correct
10 Correct 4173 ms 57316 KB Output is correct
11 Correct 4094 ms 57096 KB Output is correct
12 Correct 4460 ms 59016 KB Output is correct
13 Correct 4350 ms 55904 KB Output is correct
14 Correct 3932 ms 57424 KB Output is correct
15 Correct 905 ms 108372 KB Output is correct
16 Execution timed out 20044 ms 106288 KB Time limit exceeded
17 Halted 0 ms 0 KB -