oj.uz

Submission #168069

# Submission time Handle Problem Language Result Execution time Memory
168069 2019-12-11T08:59:02 Z davitmarg Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 24972 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];
int 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;
            used[i][j] = 0;
        }

    priority_queue<pair<int, 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)
{
    if (m != 1)
        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];
        }
    if (m == 1)
        djikstra(0);
}

#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 19 ms 20088 KB Output is correct
2 Incorrect 19 ms 20088 KB Output isn't correct
3 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 27 ms 544 KB Output is correct
5 Correct 12 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 27 ms 504 KB Output is correct
8 Correct 17 ms 504 KB Output is correct
9 Correct 20 ms 376 KB Output is correct
10 Correct 18 ms 504 KB Output is correct
11 Correct 9317 ms 3016 KB Output is correct
12 Correct 27 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1016 KB Output is correct
2 Correct 261 ms 1196 KB Output is correct
3 Correct 154 ms 888 KB Output is correct
4 Correct 153 ms 976 KB Output is correct
5 Correct 151 ms 968 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 235 ms 1016 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 726 ms 24164 KB Output is correct
2 Correct 1603 ms 24096 KB Output is correct
3 Correct 738 ms 24180 KB Output is correct
4 Execution timed out 20082 ms 24772 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 888 KB Output is correct
2 Correct 260 ms 1144 KB Output is correct
3 Correct 154 ms 1004 KB Output is correct
4 Correct 153 ms 968 KB Output is correct
5 Correct 152 ms 968 KB Output is correct
6 Correct 748 ms 24116 KB Output is correct
7 Correct 1626 ms 24116 KB Output is correct
8 Correct 764 ms 24124 KB Output is correct
9 Execution timed out 20023 ms 24968 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 892 KB Output is correct
2 Correct 259 ms 1184 KB Output is correct
3 Correct 154 ms 1016 KB Output is correct
4 Correct 154 ms 1000 KB Output is correct
5 Correct 151 ms 1008 KB Output is correct
6 Correct 748 ms 24184 KB Output is correct
7 Correct 1611 ms 24188 KB Output is correct
8 Correct 729 ms 24312 KB Output is correct
9 Execution timed out 20085 ms 24972 KB Time limit exceeded
10 Halted 0 ms 0 KB -