#include <bits/stdc++.h>
using namespace std;
#include "wombats.h"
#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
int n, m;
vector<vector<int>> hor, vert;
struct segTree
{
struct Node
{
vector<vector<int>> dist;
};
vector<Node> tree;
int sz = 0;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz);
}
void merge(Node &res, Node &a, Node &b)
{
if (b.dist.size() == 0)
{
res = a;
return;
}
int c = a.dist.size();
if (res.dist.size() == 0)
res.dist.resize(c, vector<int>(c));
for (int i = 0; i < c; ++i)
for (int j = 0; j < c; ++j)
{
res.dist[i][j] = 1e9 + 500;
for (int p = 0; p < c; ++p)
{
res.dist[i][j] = min(a.dist[i][p] + b.dist[p][j], res.dist[i][j]);
}
}
}
void set(int pos, vector<vector<int>> &dists, int v, int lv, int rv)
{
if (rv - lv == 1)
{
tree[v].dist = dists;
return;
}
int m = (lv + rv) >> 1;
if (pos < m)
set(pos, dists, v * 2 + 1, lv, m);
else
set(pos, dists, v * 2 + 2, m, rv);
merge(tree[v], tree[v * 2 + 1], tree[v * 2 + 2]);
// cout << lv << " " << rv << ":\n";
// for (int i = 0; i < tree[v].dist.size(); ++i)
// for (int j = 0; j < tree[v].dist.size(); ++j)
// cout << i << " " << j << ": " << tree[v].dist[i][j] << "\n";
// cout << "\n";
}
void set(int pos, vector<vector<int>> &dists)
{
set(pos, dists, 0, 0, sz);
}
};
segTree tree;
vector<vector<int>> calc(int x)
{
vector<vector<int>> dists(m, vector<int>(m, 1e9 + 100));
for (int i = 0; i < m; ++i)
{
vector<int> dist(2 * m, 1e9 + 10);
dist[i] = 0;
priority_queue<pii> q;
q.push({0, i});
while (q.size())
{
auto [bf, el] = q.top();
q.pop();
if (dist[el] != -bf)
continue;
if (el < m and dist[el + m] > dist[el] + vert[x][el])
{
dist[el + m] = dist[el] + vert[x][el];
q.push({-dist[el + m], el + m});
}
if (el % m != 0 and dist[el - 1] > dist[el] + hor[x + el / m][(el % m) - 1])
{
dist[el - 1] = dist[el] + hor[x + el / m][(el % m) - 1];
q.push({-dist[el - 1], el - 1});
}
if (el % m != m - 1 and dist[el + 1] > dist[el] + hor[x + el / m][el % m])
{
dist[el + 1] = dist[el] + hor[x + el / m][el % m];
q.push({-dist[el + 1], el + 1});
}
}
for (int j = 0; j < m; ++j)
dists[i][j] = dist[m + j];
}
return dists;
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
n = R;
m = C;
tree.init(n);
hor.resize(n + 1, vector<int>(m));
vert.resize(n + 1, vector<int>(m));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (j + 1 < m)
hor[i][j] = H[i][j];
if (i + 1 < n)
vert[i][j] = V[i][j];
}
for (int i = 0; i + 1 < n; ++i)
{
vector<vector<int>> cur = calc(i);
// cout << i << ":\n";
// for (int i = 0; i < m; ++i)
// for (int j = 0; j < m; ++j)
// cout << i << " " << j << ": "
// << cur[i][j] << "\n";
// cout << "\n";
// cout << "!\n";
// exit(0);
tree.set(i, cur);
}
}
void changeH(int P, int Q, int W)
{
/* ... */
hor[P][Q] = W;
if (P)
{
vector<vector<int>> cur = calc(P - 1);
tree.set(P - 1, cur);
}
if (P != n - 1)
{
vector<vector<int>> cur = calc(P);
tree.set(P, cur);
}
}
void changeV(int P, int Q, int W)
{
/* ... */
vert[P][Q] = W;
if (P)
{
vector<vector<int>> cur = calc(P - 1);
tree.set(P - 1, cur);
}
if (P != n - 1)
{
vector<vector<int>> cur = calc(P);
tree.set(P, cur);
}
}
int escape(int V1, int V2)
{
return tree.tree[0].dist[V1][V2];
}
/////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <vector>
#include "wombats.h"
static int H[5000][200];
static int V[5000][200];
int main()
{
int R, C, E, P, Q, W, V1, V2, event, i, j;
assert(scanf("%d%d", &R, &C) == 2);
for (i = 0; i < R; ++i)
for (j = 0; j < C - 1; ++j)
assert(scanf("%d", &H[i][j]) == 1);
for (i = 0; i < R - 1; ++i)
for (j = 0; j < C; ++j)
assert(scanf("%d", &V[i][j]) == 1);
init(R, C, H, V);
std::vector<int> answers;
assert(scanf("%d", &E) == 1);
for (i = 0; i < E; i++)
{
assert(scanf("%d", &event) == 1);
if (event == 1)
{
assert(scanf("%d%d%d", &P, &Q, &W) == 3);
changeH(P, Q, W);
}
else if (event == 2)
{
assert(scanf("%d%d%d", &P, &Q, &W) == 3);
changeV(P, Q, W);
}
else if (event == 3)
{
assert(scanf("%d%d", &V1, &V2) == 2);
answers.push_back(escape(V1, V2));
}
}
for (int ans : answers)
{
printf("%d\n", ans);
}
return 0;
}
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;
| ^~~
/usr/bin/ld: /tmp/ccO2X2dg.o: in function `main':
wombats.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvw4kch.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
