oj.uz

Submission #168075

# Submission time Handle Problem Language Result Execution time Memory
168075 2019-12-11T09:09:44 Z davitmarg Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 24904 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], add;

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)
{
    add -= v[P][Q];
    v[P][Q] = W;
    add += v[P][Q];
}

int escape(int v1, int v2)
{
    if (m == 1)
        return add;
    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];
            add += 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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 83 ms 14456 KB Output is correct
4 Correct 13 ms 12280 KB Output is correct
5 Correct 13 ms 12152 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

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 380 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 376 KB Output is correct
6 Correct 13 ms 376 KB Output is correct
7 Correct 28 ms 504 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 20 ms 376 KB Output is correct
10 Correct 18 ms 376 KB Output is correct
11 Correct 9213 ms 1604 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 151 ms 880 KB Output is correct
2 Correct 260 ms 1044 KB Output is correct
3 Correct 152 ms 888 KB Output is correct
4 Correct 158 ms 888 KB Output is correct
5 Correct 149 ms 888 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 234 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 731 ms 24012 KB Output is correct
2 Correct 1595 ms 24032 KB Output is correct
3 Correct 723 ms 24084 KB Output is correct
4 Execution timed out 20100 ms 24724 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 1016 KB Output is correct
2 Correct 260 ms 1116 KB Output is correct
3 Correct 152 ms 1016 KB Output is correct
4 Correct 152 ms 888 KB Output is correct
5 Correct 151 ms 892 KB Output is correct
6 Correct 716 ms 24184 KB Output is correct
7 Correct 1609 ms 24088 KB Output is correct
8 Correct 734 ms 24104 KB Output is correct
9 Execution timed out 20019 ms 24904 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 888 KB Output is correct
2 Correct 261 ms 1168 KB Output is correct
3 Correct 154 ms 888 KB Output is correct
4 Correct 152 ms 972 KB Output is correct
5 Correct 150 ms 888 KB Output is correct
6 Correct 730 ms 24204 KB Output is correct
7 Correct 1624 ms 24184 KB Output is correct
8 Correct 729 ms 24144 KB Output is correct
9 Execution timed out 20087 ms 24484 KB Time limit exceeded
10 Halted 0 ms 0 KB -