oj.uz

Submission #367166

# Submission time Handle Problem Language Result Execution time Memory
367166 2021-02-16T12:08:26 Z idk321 Wombats (IOI13_wombats) C++11
0 / 100
 88 ms 82156 KB 
#include "wombats.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MA = 1000000000;
const int N = 5005;
const int M = 205;
const int NM = 1026025;
int n;
int m;
int h[N][M];
int v[N][M];
int between[M][M];
vector<array<int, 2>> adj[NM];

void makeGraph()
{
    for (int i = 0; i < NM; i++)
    {
        adj[i].clear();
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (i != n - 1)
            {
                adj[i * m + j].push_back({(i + 1) * m + j, v[i][j]});
            }
            if (j != m - 1)
            {
                adj[i * m + j].push_back({i * m + j + 1, h[i][j]});
                adj[i * m + j + 1].push_back({i * m + j, h[i][j]});
            }
        }
    }
}

int djikstra(int node)
{
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    vector<int> dist(n * m, MA);
    pq.push({0, node});

    while(!pq.empty())
    {
        auto cur = pq.top();
        pq.pop();
        int cnode = cur[1];
        int cdist = cur[0];
        if (dist[cnode] != MA) continue;
        //cout << cnode / m << " " << " " << cnode % m << " "<< cdist << " " << adj[cnode].size()<< endl;
        dist[cnode] = cdist;
        for (auto next : adj[cnode])
        {
            //if (cnode == 0) cout << next[0] << " " << dist[next[0]] << endl;
            if (dist[next[0]] != MA) continue;
            pq.push({next[1] + cdist, next[0]});

        }
    }

    for (int j = 0; j < m; j++)
    {
        between[node][j] = dist[(n - 1) * m + j];
    }
    //for (int i = 0; i < m; i++) cout << node << " " << between[node][i] << endl;
}

void build()
{
    makeGraph();
    for (int i = 0; i < m; i++) djikstra(i);
}

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 <= 20) build();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    if (m <= 20) build();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    if (m <= 20) build();
}

int escape(int V1, int V2) {
    if (m > 20)
    {
        makeGraph();
        djikstra(V1);
    }

    return between[V1][V2];
}

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 function 'int djikstra(int)':
wombats.cpp:70:1: warning: no return statement in function returning non-void [-Wreturn-type]
   70 | }
      | ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 73836 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 49388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 51052 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 82156 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 51112 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 51052 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -