| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 590339 |
2022-07-05T21:00:09 Z |
Temmie |
Wombats (IOI13_wombats) |
C++17 |
|
20000 ms |
10120 KB |
#include "wombats.h"
#include <bits/stdc++.h>
struct Dsu {
std::vector <int> p;
Dsu(int s) {
p.resize(s);
std::iota(p.begin(), p.end(), 0);
}
inline int find(int v) {
return v == p[v] ? v : (p[v] = find(p[v]));
}
inline void unite(int u, int v) {
u = find(u);
v = find(v);
p[u] = v;
}
};
int r, c;
std::vector <std::vector <int>> h, v;
std::vector <std::vector <int>> ans;
std::bitset <5000 * 200> vis;
void calculate() {
for (int s = 0; s < c; s++) {
vis.reset();
std::priority_queue <std::pair <int, std::pair <int, int>>> pq;
pq.push({ 0, { 0, s } });
while (pq.size()) {
int w = -pq.top().first;
int i = pq.top().second.first;
int j = pq.top().second.second;
pq.pop();
if (vis[i * c + j]) {
continue;
}
vis[i * c + j] = 1;
if (i == r - 1) {
ans[s][j] = w;
}
if (j) pq.push({ -w - h[i][j - 1], { i, j - 1 } });
if (j + 1 < c) pq.push({ -w - h[i][j], { i, j + 1 } });
if (i + 1 < r) pq.push({ -w - v[i][j], { i + 1, j } });
}
}
}
//void calculate() {
//ans = std::vector <std::vector <int>> (c, std::vector <int> (c, 1001));
//Dsu dsu(r * c);
//std::vector <std::set <int>> reach(r * c);
//for (int j = 0; j < c; j++) {
//reach[j].insert(j);
//reach[(r - 1) * c + j].insert((r - 1) * c + j);
//}
//std::vector <std::vector <int>> of(1001);
//for (int i = 0; i < r; i++) {
//for (int j = 0; j < c; j++) {
//if (i < r - 1) {
//of[v[i][j]].push_back(i * c + j);
//}
//if (j < c - 1) {
//of[h[i][j]].push_back(i * c + j);
//}
//}
//}
//std::vector <std::set <int>> nodes(r * c);
//for (int i = 0; i < r; i++) {
//for (int j = 0; j < c; j++) {
//nodes[i * c + j].insert(i * c + j);
//}
//}
//for (int k = 0; k <= 1000; k++) {
//for (int x : of[k]) {
//int v1 = x;
//std::vector <int> v2s;
//if (x / c < r - 1 && v[x / c][x % c] == k) {
//v2s.push_back(x + c);
//}
//if (x % c < c - 1 && h[x / c][x % c] == k) {
//v2s.push_back(x + 1);
//}
//for (int v2 : v2s) {
//int u1 = dsu.find(v1);
//int u2 = dsu.find(v2);
//if (u1 == u2) {
//continue;
//}
//for (int y : reach[u1]) {
//if (y >= (r - 1) * c) {
//for (auto it = nodes[u2].begin(); it != nodes[u2].end() && *it < c; it++) {
//ans[*it][y - (r - 1) * c] = std::min(ans[*it][y - (r - 1) * c], k);
//}
//}
//}
//for (int y : reach[u2]) {
//if (y >= (r - 1) * c) {
//for (auto it = nodes[u1].begin(); it != nodes[u1].end() && *it < c; it++) {
//ans[*it][y - (r - 1) * c] = std::min(ans[*it][y - (r - 1) * c], k);
//}
//}
//}
//if (nodes[u1].size() < nodes[u2].size()) {
//std::swap(nodes[u1], nodes[u2]);
//}
//for (int y : nodes[u2]) {
//nodes[u1].insert(y);
//}
//if (reach[u1].size() < reach[u2].size()) {
//std::swap(reach[u1], reach[u2]);
//}
//for (int y : reach[u2]) {
//reach[u1].insert(y);
//}
//nodes[u2].clear();
//reach[u2].clear();
//dsu.unite(u2, u1);
//}
//}
//}
//}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
r = R;
c = C;
ans.resize(c, std::vector <int> (c));
h.resize(r, std::vector <int> (c - 1));
v.resize(r - 1, std::vector <int> (c));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (j < c - 1) {
h[i][j] = H[i][j];
}
if (i < r - 1) {
v[i][j] = V[i][j];
}
}
}
calculate();
}
void changeH(int p, int q, int w) {
h[p][q] = w;
calculate();
}
void changeV(int p, int q, int w) {
v[p][q] = w;
calculate();
}
int escape(int v1, int v2) {
return ans[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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
4812 KB |
Output is correct |
| 2 |
Correct |
56 ms |
4752 KB |
Output is correct |
| 3 |
Correct |
118 ms |
7424 KB |
Output is correct |
| 4 |
Correct |
55 ms |
4692 KB |
Output is correct |
| 5 |
Correct |
56 ms |
4748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
440 KB |
Output is correct |
| 6 |
Correct |
4 ms |
468 KB |
Output is correct |
| 7 |
Correct |
2 ms |
468 KB |
Output is correct |
| 8 |
Correct |
2 ms |
468 KB |
Output is correct |
| 9 |
Correct |
3 ms |
468 KB |
Output is correct |
| 10 |
Correct |
2 ms |
436 KB |
Output is correct |
| 11 |
Correct |
66 ms |
2764 KB |
Output is correct |
| 12 |
Correct |
2 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20004 ms |
804 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
804 ms |
8908 KB |
Output is correct |
| 2 |
Correct |
1478 ms |
8852 KB |
Output is correct |
| 3 |
Correct |
800 ms |
8852 KB |
Output is correct |
| 4 |
Correct |
844 ms |
10120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20083 ms |
808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20008 ms |
808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
