| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 941055 | vjudge1 | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#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
#include "wombats.h"
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));
vector<vector<int>> opt(m, vector<int>(m));
for (int val = -(c + 1); val < c; ++val)
for (int i = 0; i < c; ++i)
{
int j = i - val;
if (j >= 0 and j < c)
{
res.dist[i][j] = 1e9 + 500;
int L = i ? opt[i - 1][j] : 0;
int R = j + 1 < c ? opt[i][j + 1] : m - 1;
for (int p = 0; p < c; ++p)
if (res.dist[i][j] > a.dist[i][p] + b.dist[p][j])
{
res.dist[i][j] = a.dist[i][p] + b.dist[p][j];
opt[i][j] = p;
}
}
}
}
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;
dists.resize(m, vector<int>(m, 1e9 + 10));
int l = x;
int r = min(x + 20, n - 1);
vector<int> newD(m);
for (int st = 0; st < m; ++st)
{
auto &d = dists[st];
d[st] = 0;
for (int i = 1; i < m; ++i)
d[i] = min(d[i], d[i - 1] + hor[l][i - 1]);
for (int i = m - 2; i >= 0; --i)
d[i] = min(d[i], d[i + 1] + hor[l][i]);
for (int x = l; x < r; ++x)
{
for (int i = 0; i < m; ++i)
newD[i] = d[i] + vert[x][i];
for (int i = 1; i < m; ++i)
newD[i] = min(newD[i], newD[i - 1] + hor[x + 1][i - 1]);
for (int i = m - 2; i >= 0; --i)
newD[i] = min(newD[i], newD[i + 1] + hor[x + 1][i]);
d = newD;
}
}
return dists;
}
void init(int R, int C, int H[5000][200], int V[5000][200])
{
n = R;
m = C;
tree.init((n + 19) / 20);
hor.resize(n + 1, vector<int>(m + 1));
vert.resize(n + 1, vector<int>(m + 1));
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 += 20)
{
vector<vector<int>> cur = calc(i);
tree.set(i / 20, cur);
}
// cout << "!\n";
// exit(0);
}
void changeH(int P, int Q, int W)
{
/* ... */
hor[P][Q] = W;
if (P % 20 != 0 or P != n - 1)
{
vector<vector<int>> cur = calc(P / 20);
tree.set(P / 20, cur);
}
if (P % 20 == 0 and P > 0)
{
vector<vector<int>> cur = calc((P - 1) / 20);
tree.set((P - 1) / 20, cur);
}
}
void changeV(int P, int Q, int W)
{
/* ... */
vert[P][Q] = W;
if (P % 20 != 0 or P != n - 1)
{
vector<vector<int>> cur = calc(P / 20);
tree.set(P / 20, cur);
}
if (P % 20 == 0 and P > 0)
{
vector<vector<int>> cur = calc((P - 1) / 20);
tree.set((P - 1) / 20, 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;
}