oj.uz

Submission #940441

# Submission time Handle Problem Language Result Execution time Memory
940441 2024-03-07T09:17:57 Z vjudge1 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#include "wombats.h"

#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back

int n, m;
vector<vector<int>> hor, vert;

struct segTree
{
    struct Node
    {
        vector<vector<int>> dist;
    };
    vector<Node> tree;
    int sz = 0;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz);
    }

    void merge(Node &res, Node &a, Node &b)
    {
        if (b.dist.size() == 0)
        {
            res = a;
            return;
        }

        int c = a.dist.size();

        if (res.dist.size() == 0)
            res.dist.resize(c, vector<int>(c));

        for (int i = 0; i < c; ++i)
            for (int j = 0; j < c; ++j)
            {
                res.dist[i][j] = 1e9 + 500;
                for (int p = 0; p < c; ++p)
                {
                    res.dist[i][j] = min(a.dist[i][p] + b.dist[p][j], res.dist[i][j]);
                }
            }
    }

    void set(int pos, vector<vector<int>> &dists, int v, int lv, int rv)
    {
        if (rv - lv == 1)
        {
            tree[v].dist = dists;
            return;
        }
        int m = (lv + rv) >> 1;
        if (pos < m)
            set(pos, dists, v * 2 + 1, lv, m);
        else
            set(pos, dists, v * 2 + 2, m, rv);
        merge(tree[v], tree[v * 2 + 1], tree[v * 2 + 2]);
        // cout << lv << " " << rv << ":\n";
        // for (int i = 0; i < tree[v].dist.size(); ++i)
        //     for (int j = 0; j < tree[v].dist.size(); ++j)
        //         cout << i << " " << j << ": " << tree[v].dist[i][j] << "\n";

        // cout << "\n";
    }

    void set(int pos, vector<vector<int>> &dists)
    {
        set(pos, dists, 0, 0, sz);
    }
};

segTree tree;

vector<vector<int>> calc(int x)
{
    vector<vector<int>> dists(m, vector<int>(m, 1e9 + 100));
    for (int i = 0; i < m; ++i)
    {
        vector<int> dist(2 * m, 1e9 + 10);
        dist[i] = 0;
        priority_queue<pii> q;
        q.push({0, i});
        while (q.size())
        {
            auto [bf, el] = q.top();
            q.pop();
            if (dist[el] != -bf)
                continue;
            if (el < m and dist[el + m] > dist[el] + vert[x][el])
            {
                dist[el + m] = dist[el] + vert[x][el];
                q.push({-dist[el + m], el + m});
            }
            if (el % m != 0 and dist[el - 1] > dist[el] + hor[x + el / m][(el % m) - 1])
            {
                dist[el - 1] = dist[el] + hor[x + el / m][(el % m) - 1];
                q.push({-dist[el - 1], el - 1});
            }
            if (el % m != m - 1 and dist[el + 1] > dist[el] + hor[x + el / m][el % m])
            {
                dist[el + 1] = dist[el] + hor[x + el / m][el % m];
                q.push({-dist[el + 1], el + 1});
            }
        }
        for (int j = 0; j < m; ++j)
            dists[i][j] = dist[m + j];
    }
    return dists;
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
    n = R;
    m = C;

    tree.init(n);

    hor.resize(n + 1, vector<int>(m));
    vert.resize(n + 1, vector<int>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            if (j + 1 < m)
                hor[i][j] = H[i][j];
            if (i + 1 < n)
                vert[i][j] = V[i][j];
        }

    for (int i = 0; i + 1 < n; ++i)
    {
        vector<vector<int>> cur = calc(i);
        // cout << i << ":\n";
        // for (int i = 0; i < m; ++i)
        //     for (int j = 0; j < m; ++j)
        //         cout << i << " " << j << ": "
        //              << cur[i][j] << "\n";
        // cout << "\n";
        // cout << "!\n";
        // exit(0);
        tree.set(i, cur);
    }
}

void changeH(int P, int Q, int W)
{
    /* ... */
    hor[P][Q] = W;
    if (P)
    {
        vector<vector<int>> cur = calc(P - 1);
        tree.set(P - 1, cur);
    }
    if (P != n - 1)
    {
        vector<vector<int>> cur = calc(P);
        tree.set(P, cur);
    }
}

void changeV(int P, int Q, int W)
{
    /* ... */
    vert[P][Q] = W;
    if (P)
    {
        vector<vector<int>> cur = calc(P - 1);
        tree.set(P - 1, cur);
    }
    if (P != n - 1)
    {
        vector<vector<int>> cur = calc(P);
        tree.set(P, cur);
    }
}

int escape(int V1, int V2)
{
    return tree.tree[0].dist[V1][V2];
}

// /////////////////////////////

// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include <vector>
// #include "wombats.h"

// static int H[5000][200];
// static int V[5000][200];

// int main()
// {
//     int R, C, E, P, Q, W, V1, V2, event, i, j;

//     assert(scanf("%d%d", &R, &C) == 2);
//     for (i = 0; i < R; ++i)
//         for (j = 0; j < C - 1; ++j)
//             assert(scanf("%d", &H[i][j]) == 1);
//     for (i = 0; i < R - 1; ++i)
//         for (j = 0; j < C; ++j)
//             assert(scanf("%d", &V[i][j]) == 1);

//     init(R, C, H, V);

//     std::vector<int> answers;

//     assert(scanf("%d", &E) == 1);
//     for (i = 0; i < E; i++)
//     {
//         assert(scanf("%d", &event) == 1);
//         if (event == 1)
//         {
//             assert(scanf("%d%d%d", &P, &Q, &W) == 3);
//             changeH(P, Q, W);
//         }
//         else if (event == 2)
//         {
//             assert(scanf("%d%d%d", &P, &Q, &W) == 3);
//             changeV(P, Q, W);
//         }
//         else if (event == 3)
//         {
//             assert(scanf("%d%d", &V1, &V2) == 2);
//             answers.push_back(escape(V1, V2));
//         }
//     }
//     for (int ans : answers)
//     {
//         printf("%d\n", ans);
//     }
//     return 0;
// }

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 4 ms 6232 KB Output is correct
2 Correct 5 ms 6236 KB Output is correct
3 Correct 58 ms 9040 KB Output is correct
4 Correct 6 ms 6232 KB Output is correct
5 Correct 7 ms 6232 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2612 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 54 ms 4872 KB Output is correct
12 Correct 2 ms 2392 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1787 ms 11588 KB Output is correct
2 Correct 1921 ms 11452 KB Output is correct
3 Correct 1839 ms 11428 KB Output is correct
4 Correct 1851 ms 11424 KB Output is correct
5 Correct 1808 ms 11348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 8224 ms 11428 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10440 KB Output is correct
2 Correct 14 ms 10332 KB Output is correct
3 Correct 14 ms 10328 KB Output is correct
4 Correct 36 ms 11868 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2054 ms 11476 KB Output is correct
2 Correct 1953 ms 11360 KB Output is correct
3 Correct 1845 ms 11420 KB Output is correct
4 Correct 1856 ms 11416 KB Output is correct
5 Correct 1837 ms 11336 KB Output is correct
6 Correct 9 ms 10328 KB Output is correct
7 Correct 9 ms 10332 KB Output is correct
8 Correct 11 ms 10360 KB Output is correct
9 Correct 37 ms 11860 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 5 ms 6236 KB Output is correct
12 Correct 58 ms 9072 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 6236 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 2 ms 2596 KB Output is correct
22 Correct 2 ms 2396 KB Output is correct
23 Correct 2 ms 2392 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct
25 Correct 55 ms 4944 KB Output is correct
26 Correct 2 ms 2396 KB Output is correct
27 Correct 8265 ms 11424 KB Output is correct
28 Runtime error 19842 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1852 ms 11336 KB Output is correct
2 Correct 1922 ms 11236 KB Output is correct
3 Correct 1852 ms 11420 KB Output is correct
4 Correct 1859 ms 11424 KB Output is correct
5 Correct 1847 ms 11088 KB Output is correct
6 Correct 14 ms 10332 KB Output is correct
7 Correct 9 ms 10440 KB Output is correct
8 Correct 9 ms 10332 KB Output is correct
9 Correct 37 ms 11748 KB Output is correct
10 Correct 5 ms 6236 KB Output is correct
11 Correct 4 ms 6236 KB Output is correct
12 Correct 58 ms 8924 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 6236 KB Output is correct
15 Execution timed out 20057 ms 204036 KB Time limit exceeded
16 Halted 0 ms 0 KB -