oj.uz

답안 #940482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940482 2024-03-07T09:47:48 Z Der_Vlapos 웜뱃 (IOI13_wombats) C++17
39 / 100
 20000 ms 61424 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")

#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));

        vector<vector<int>> opt(m, vector<int>(m));

        for (int val = -(c + 1); val < c; ++val)
            for (int i = 0; i < c; ++i)
            {
                int j = i - val;

                if (j >= 0 and j < c)
                {
                    res.dist[i][j] = 1e9 + 500;
                    int L = i ? opt[i - 1][j] : 0;
                    int R = j + 1 < c ? opt[i][j + 1] : m - 1;
                    for (int p = 0; p < c; ++p)
                        if (res.dist[i][j] > a.dist[i][p] + b.dist[p][j])
                        {
                            res.dist[i][j] = a.dist[i][p] + b.dist[p][j];
                            opt[i][j] = p;
                        }
                }
            }
    }

    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)
{
    if (x == n - 1)
        exit(0);

    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 + 1));
    vert.resize(n + 1, vector<int>(m + 1));
    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;
      |      ^~~
wombats.cpp: In member function 'void segTree::merge(segTree::Node&, segTree::Node&, segTree::Node&)':
wombats.cpp:59:25: warning: unused variable 'L' [-Wunused-variable]
   59 |                     int L = i ? opt[i - 1][j] : 0;
      |                         ^
wombats.cpp:60:25: warning: unused variable 'R' [-Wunused-variable]
   60 |                     int R = j + 1 < c ? opt[i][j + 1] : m - 1;
      |                         ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6236 KB Output is correct
2 Correct 9 ms 6204 KB Output is correct
3 Correct 61 ms 7764 KB Output is correct
4 Correct 9 ms 6236 KB Output is correct
5 Correct 10 ms 6248 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 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 4 ms 2580 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 4 ms 2568 KB Output is correct
7 Correct 4 ms 2396 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 4 ms 2396 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 58 ms 3460 KB Output is correct
12 Correct 4 ms 2396 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10047 ms 11572 KB Output is correct
2 Correct 8045 ms 11304 KB Output is correct
3 Correct 10222 ms 11388 KB Output is correct
4 Correct 10191 ms 11412 KB Output is correct
5 Correct 10060 ms 11596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 20082 ms 11680 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 10332 KB Output is correct
2 Correct 18 ms 10332 KB Output is correct
3 Correct 18 ms 10332 KB Output is correct
4 Correct 46 ms 11120 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9958 ms 11296 KB Output is correct
2 Correct 7979 ms 11392 KB Output is correct
3 Correct 10351 ms 11388 KB Output is correct
4 Correct 10215 ms 11384 KB Output is correct
5 Correct 10018 ms 11680 KB Output is correct
6 Correct 18 ms 10332 KB Output is correct
7 Correct 18 ms 10336 KB Output is correct
8 Correct 19 ms 10352 KB Output is correct
9 Correct 48 ms 11092 KB Output is correct
10 Correct 9 ms 6232 KB Output is correct
11 Correct 10 ms 6236 KB Output is correct
12 Correct 61 ms 7612 KB Output is correct
13 Correct 9 ms 6236 KB Output is correct
14 Correct 9 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 348 KB Output is correct
18 Correct 4 ms 2396 KB Output is correct
19 Correct 3 ms 2396 KB Output is correct
20 Correct 3 ms 2396 KB Output is correct
21 Correct 4 ms 2396 KB Output is correct
22 Correct 3 ms 2396 KB Output is correct
23 Correct 4 ms 2396 KB Output is correct
24 Correct 3 ms 2488 KB Output is correct
25 Correct 59 ms 3412 KB Output is correct
26 Correct 4 ms 2392 KB Output is correct
27 Execution timed out 20096 ms 11492 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9990 ms 11304 KB Output is correct
2 Correct 8020 ms 11432 KB Output is correct
3 Correct 10215 ms 11652 KB Output is correct
4 Correct 10220 ms 11576 KB Output is correct
5 Correct 10107 ms 11552 KB Output is correct
6 Correct 20 ms 10328 KB Output is correct
7 Correct 19 ms 10328 KB Output is correct
8 Correct 20 ms 10224 KB Output is correct
9 Correct 52 ms 11224 KB Output is correct
10 Correct 9 ms 6236 KB Output is correct
11 Correct 10 ms 6236 KB Output is correct
12 Correct 67 ms 7668 KB Output is correct
13 Correct 10 ms 6236 KB Output is correct
14 Correct 9 ms 6236 KB Output is correct
15 Execution timed out 20051 ms 61424 KB Time limit exceeded
16 Halted 0 ms 0 KB -