oj.uz

Submission #168074

# Submission time Handle Problem Language Result Execution time Memory
168074 2019-12-11T09:08:37 Z davitmarg Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 24836 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)
        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;
      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:106:12: warning: statement has no effect [-Wunused-value]
         add;
            ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 20088 KB Output is correct
2 Correct 153 ms 20088 KB Output is correct
3 Execution timed out 20027 ms 21592 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 13 ms 504 KB Output is correct
7 Correct 29 ms 504 KB Output is correct
8 Correct 17 ms 504 KB Output is correct
9 Correct 20 ms 504 KB Output is correct
10 Correct 18 ms 504 KB Output is correct
11 Correct 9394 ms 1748 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 884 KB Output is correct
2 Correct 263 ms 1276 KB Output is correct
3 Correct 155 ms 1016 KB Output is correct
4 Correct 154 ms 988 KB Output is correct
5 Correct 153 ms 888 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 239 ms 1116 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 719 ms 24184 KB Output is correct
2 Correct 1641 ms 24184 KB Output is correct
3 Correct 729 ms 24184 KB Output is correct
4 Execution timed out 20014 ms 24612 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 960 KB Output is correct
2 Correct 264 ms 1348 KB Output is correct
3 Correct 154 ms 988 KB Output is correct
4 Correct 155 ms 860 KB Output is correct
5 Correct 152 ms 972 KB Output is correct
6 Correct 733 ms 24312 KB Output is correct
7 Correct 1634 ms 24084 KB Output is correct
8 Correct 724 ms 24168 KB Output is correct
9 Execution timed out 20049 ms 24616 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 964 KB Output is correct
2 Correct 264 ms 1304 KB Output is correct
3 Correct 154 ms 888 KB Output is correct
4 Correct 155 ms 1016 KB Output is correct
5 Correct 154 ms 888 KB Output is correct
6 Correct 733 ms 24080 KB Output is correct
7 Correct 1637 ms 24184 KB Output is correct
8 Correct 725 ms 24088 KB Output is correct
9 Execution timed out 20103 ms 24836 KB Time limit exceeded
10 Halted 0 ms 0 KB -