Submission #367166

#	Time	Username	Problem	Language	Result	Execution time	Memory
367166		idk321	Wombats (IOI13_wombats)	C++11	0 / 100	88 ms	82156 KiB

wombats

#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 (stderr)

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24