| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1074149 |
2024-08-25T08:23:20 Z |
1ne |
웜뱃 (IOI13_wombats) |
C++14 |
|
20000 ms |
166068 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<200;++i){
for (int j = 0;j<500;++j){
for (int k = 0;k<200;++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<200;++i){
for (int j = 0;j<500;++j){
for (int k = 0;k<200;++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<200;++i){
for (int j = 0;j<500;++j){
for (int k = 0;k<200;++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;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11278 ms |
161504 KB |
Output is correct |
| 2 |
Correct |
11178 ms |
161516 KB |
Output is correct |
| 3 |
Correct |
11212 ms |
164180 KB |
Output is correct |
| 4 |
Correct |
11233 ms |
161508 KB |
Output is correct |
| 5 |
Correct |
11089 ms |
161368 KB |
Output is correct |
| 6 |
Correct |
79 ms |
158544 KB |
Output is correct |
| 7 |
Correct |
90 ms |
158544 KB |
Output is correct |
| 8 |
Correct |
74 ms |
158544 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
84 ms |
158412 KB |
Output is correct |
| 2 |
Correct |
84 ms |
158476 KB |
Output is correct |
| 3 |
Correct |
81 ms |
158496 KB |
Output is correct |
| 4 |
Correct |
81 ms |
159232 KB |
Output is correct |
| 5 |
Correct |
78 ms |
160592 KB |
Output is correct |
| 6 |
Correct |
101 ms |
159056 KB |
Output is correct |
| 7 |
Correct |
86 ms |
159208 KB |
Output is correct |
| 8 |
Correct |
83 ms |
159040 KB |
Output is correct |
| 9 |
Correct |
106 ms |
160604 KB |
Output is correct |
| 10 |
Correct |
88 ms |
159228 KB |
Output is correct |
| 11 |
Correct |
134 ms |
161572 KB |
Output is correct |
| 12 |
Correct |
84 ms |
160600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17355 ms |
160204 KB |
Output is correct |
| 2 |
Execution timed out |
20084 ms |
160204 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
20077 ms |
166068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17480 ms |
160208 KB |
Output is correct |
| 2 |
Execution timed out |
20067 ms |
158232 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17332 ms |
160208 KB |
Output is correct |
| 2 |
Execution timed out |
20065 ms |
159972 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
