| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1074155 |
2024-08-25T08:26:58 Z |
1ne |
Wombats (IOI13_wombats) |
C++14 |
|
20000 ms |
19860 KB |
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y,d;
};
vector<vector<vector<node>>>adj;
int dist1[200][500][200];
int dist2[200][500][200];
int dist3[200][200];
int n,m;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
/* ... */
n = R,m = C;
adj.resize(R,vector<vector<node>>(C));
for (int i = 0;i<R;++i){
for (int j = 0;j<C - 1;++j){
adj[i][j].push_back({i,j + 1,H[i][j]});
adj[i][j + 1].push_back({i,j,H[i][j]});
}
}
for (int i = 0;i<R - 1;++i){
for (int j = 0;j<C;++j){
adj[i][j].push_back({i + 1,j,V[i][j]});
adj[i + 1][j].push_back({i,j,V[i][j]});
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<n;++j){
for (int k = 0;k<m;++k){
dist1[i][j][k] = 1e9;
dist2[i][j][k] = 1e9;
dist3[i][k] = 1e9;
}
}
}
for (int i = 0;i<C;++i){
queue<pair<int,int>>q;
q.push({0,i});
dist1[i][0][i] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:adj[u.first][u.second]){
if (u.first - x.x > 0)continue;
if (dist1[i][x.x][x.y] > dist1[i][u.first][u.second] + x.d){
dist1[i][x.x][x.y] = dist1[i][u.first][u.second] + x.d;
q.push({x.x,x.y});
}
}
}
}
for (int i = 0;i<C;++i){
for (int j = 0;j<C;++j){
dist3[i][j] = dist1[i][n - 1][j];
}
}
for (int i = 0;i<C;++i){
queue<pair<int,int>>q;
q.push({R - 1,i});
dist2[i][R - 1][i] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:adj[u.first][u.second]){
if (u.first - x.x > 0)continue;
if (dist2[i][x.x][x.y] > dist2[i][u.first][u.second] + x.d){
dist2[i][x.x][x.y] = dist2[i][u.first][u.second] + x.d;
q.push({x.x,x.y});
}
}
}
}
}
void changeH(int P, int Q, int W) {
for (auto &x:adj[P][Q]){
if (x.y == Q + 1){
x.d = W;
}
}
for (auto &x:adj[P][Q + 1]){
if (x.y == Q){
x.d = W;
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<n;++j){
for (int k = 0;k<m;++k){
dist1[i][j][k] = 1e9;
dist2[i][j][k] = 1e9;
dist3[i][k] = 1e9;
}
}
}
for (int i = 0;i<m;++i){
queue<pair<int,int>>q;
q.push({0,i});
dist1[i][0][i] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:adj[u.first][u.second]){
if (u.first - x.x > 0)continue;
if (dist1[i][x.x][x.y] > dist1[i][u.first][u.second] + x.d){
dist1[i][x.x][x.y] = dist1[i][u.first][u.second] + x.d;
q.push({x.x,x.y});
}
}
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[i][n - 1][j];
}
}
for (int i = 0;i<m;++i){
queue<pair<int,int>>q;
q.push({n - 1,i});
dist2[i][n - 1][i] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:adj[u.first][u.second]){
if (u.first - x.x > 0)continue;
if (dist2[i][x.x][x.y] > dist2[i][u.first][u.second] + x.d){
dist2[i][x.x][x.y] = dist2[i][u.first][u.second] + x.d;
q.push({x.x,x.y});
}
}
}
}
}
void changeV(int P, int Q, int W) {
for (auto &x:adj[P][Q]){
if (x.x == P + 1){
x.d = W;
}
}
for (auto &x:adj[P + 1][Q]){
if (x.x == P){
x.d = W;
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<n;++j){
for (int k = 0;k<m;++k){
dist1[i][j][k] = 1e9;
dist2[i][j][k] = 1e9;
dist3[i][k] = 1e9;
}
}
}
for (int i = 0;i<m;++i){
queue<pair<int,int>>q;
q.push({0,i});
dist1[i][0][i] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:adj[u.first][u.second]){
if (u.first - x.x > 0)continue;
if (dist1[i][x.x][x.y] > dist1[i][u.first][u.second] + x.d){
dist1[i][x.x][x.y] = dist1[i][u.first][u.second] + x.d;
q.push({x.x,x.y});
}
}
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[i][n - 1][j];
}
}
for (int i = 0;i<m;++i){
queue<pair<int,int>>q;
q.push({n - 1,i});
dist2[i][n - 1][i] = 0;
while(!q.empty()){
auto u = q.front();
q.pop();
for (auto x:adj[u.first][u.second]){
if (u.first - x.x > 0)continue;
if (dist2[i][x.x][x.y] > dist2[i][u.first][u.second] + x.d){
dist2[i][x.x][x.y] = dist2[i][u.first][u.second] + x.d;
q.push({x.x,x.y});
}
}
}
}
}
int escape(int V1, int V2) {
return dist3[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 |
56 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
61 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
92 ms |
15300 KB |
Output is correct |
| 4 |
Correct |
55 ms |
12376 KB |
Output is correct |
| 5 |
Correct |
57 ms |
12380 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 11 |
Correct |
43 ms |
2260 KB |
Output is correct |
| 12 |
Correct |
5 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13914 ms |
19856 KB |
Output is correct |
| 2 |
Execution timed out |
20066 ms |
19700 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20098 ms |
17952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13073 ms |
19860 KB |
Output is correct |
| 2 |
Execution timed out |
20053 ms |
19700 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13421 ms |
19856 KB |
Output is correct |
| 2 |
Execution timed out |
20023 ms |
17752 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
