oj.uz

Submission #168065

# Submission time Handle Problem Language Result Execution time Memory
168065 2019-12-11T08:46:22 Z davitmarg Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 36768 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000009ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 5005;

#ifndef death
#include "wombats.h"
#endif

int n, m, used[5005][202];
LL d[5005][202], h[5005][202], v[5005][202];

void djikstra(int v2)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            d[i][j] = mod * mod;
            used[i][j] = 0;
        }

    priority_queue<pair<LL, pair<int, int>>> q;

    d[n - 1][v2] = 0;
    q.push(MP(0, MP(n - 1, v2)));

    while (!q.empty())
    {
        int y = -1, x = -1;
        do
        {
            y = q.top().second.first;
            x = q.top().second.second;
            q.pop();
        } while (used[y][x] && !q.empty());

        if (y == -1 || used[y][x])
            break;
        used[y][x] = 1;

        int Y, X;

        Y = y - 1;
        X = x;
        if (y > 0 && d[Y][X] > d[y][x] + v[Y][X])
        {
            d[Y][X] = d[y][x] + v[Y][X];
            q.push(MP(-d[Y][X], MP(Y, X)));
        }

        Y = y;
        X = x + 1;
        if (x < m - 1 && d[Y][X] > d[y][x] + h[y][x])
        {
            d[Y][X] = d[y][x] + h[y][x];
            q.push(MP(-d[Y][X], MP(Y, X)));
        }

        Y = y;
        X = x - 1;
        if (x > 0 && d[Y][X] > d[y][x] + h[Y][X])
        {
            d[Y][X] = d[y][x] + h[Y][X];
            q.push(MP(-d[Y][X], MP(Y, X)));
        }
    }
}

void changeH(int P, int Q, int W)
{
    h[P][Q] = W;
}

void changeV(int P, int Q, int W)
{
    v[P][Q] = W;
}

int escape(int v1, int v2)
{
    djikstra(v2);
    return d[0][v1];
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
    n = R;
    m = C;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            h[i][j] = H[i][j];
            v[i][j] = V[i][j];
        }
}

#ifdef death

int main()
{
    int N, M, H[5000][200], V[5000][200], Q;
    cin >> N >> M;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M - 1; j++)
            cin >> H[i][j];

    for (int i = 0; i < N - 1; i++)
        for (int j = 0; j < M; j++)
            cin >> V[i][j];
    init(N, M, H, V);
    cin >> Q;
    while (Q--)
    {
        int T, Y, X, W;
        cin >> T >> Y >> X;
        if (T == 3)
        {
            cout << "!!!";
            cout << escape(Y, X) << endl;
            continue;
        }
        cin >> W;
        if (T == 1)
            changeH(Y, X, W);
        else
            changeV(Y, X, W);
    }

    return 0;
}

#endif

/*


3 4
0 2 5
7 1 1
0 4 0 
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1 
 
*/

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 31992 KB Output is correct
2 Correct 179 ms 31992 KB Output is correct
3 Execution timed out 20047 ms 33400 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 28 ms 504 KB Output is correct
5 Correct 12 ms 504 KB Output is correct
6 Correct 14 ms 504 KB Output is correct
7 Correct 27 ms 504 KB Output is correct
8 Correct 17 ms 632 KB Output is correct
9 Correct 20 ms 424 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 9645 ms 3088 KB Output is correct
12 Correct 27 ms 500 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 1160 KB Output is correct
2 Correct 258 ms 1544 KB Output is correct
3 Correct 158 ms 1144 KB Output is correct
4 Correct 158 ms 1208 KB Output is correct
5 Correct 157 ms 1244 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 241 ms 1144 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 35900 KB Output is correct
2 Correct 1729 ms 36088 KB Output is correct
3 Correct 782 ms 36088 KB Output is correct
4 Execution timed out 20010 ms 36768 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1016 KB Output is correct
2 Correct 262 ms 1540 KB Output is correct
3 Correct 158 ms 1272 KB Output is correct
4 Correct 157 ms 1144 KB Output is correct
5 Correct 155 ms 1144 KB Output is correct
6 Correct 784 ms 35960 KB Output is correct
7 Correct 1721 ms 36076 KB Output is correct
8 Correct 782 ms 36060 KB Output is correct
9 Execution timed out 20028 ms 36740 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1144 KB Output is correct
2 Correct 264 ms 1408 KB Output is correct
3 Correct 158 ms 1272 KB Output is correct
4 Correct 158 ms 1120 KB Output is correct
5 Correct 156 ms 1284 KB Output is correct
6 Correct 791 ms 36100 KB Output is correct
7 Correct 1725 ms 36088 KB Output is correct
8 Correct 790 ms 35964 KB Output is correct
9 Execution timed out 20012 ms 36684 KB Time limit exceeded
10 Halted 0 ms 0 KB -