| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1074355 |
2024-08-25T10:01:56 Z |
1ne |
Wombats (IOI13_wombats) |
C++14 |
|
20000 ms |
17496 KB |
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y,d;
};
vector<vector<vector<node>>>adj,rev_adj;
int dist3[200][200];
int n,m;
int dist1[5000][200],dist2[5000][200];
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));
rev_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]});
rev_adj[i + 1][j].push_back({i,j,V[i][j]});
}
}
int block = sqrt(n);
for (int i = 0;i<=block;++i){
for (int j = 0;j<m;++j){
dist1[i][j] = 1e9,dist2[i][j] = 1e9;
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<m;++j){
dist3[i][j] = 0;
}
}
for (int i = 0;i<m;++i){
for (int k = 0;k<n;k+=block){
int en = min(k + block - 1,n - 1);
int vv = en - k;
priority_queue<pair<int,pair<int,int>>>q;
for (int j = 0;j<block;++j){
for (int p = 0;p<m;++p){
dist1[j][p] = 1e9;
}
}
if (k == 0){
dist1[0][i] = 0;
q.push({0,{0,i}});
}
else{
for (int j = 0;j<m;++j){
for (auto x:rev_adj[k][j]){
if (x.y == j)
dist1[0][j] = dist3[i][j] + x.d;
}
//cout<<i<<" "<<k<<" "<<j<<" "<<dist1[0][j]<<" "<<dist3[i][j]<<'\n';
}
for (int j = 0;j<m;++j){
for (auto x:adj[k][j]){
if (x.x == k)
if (dist1[0][x.y] > dist1[0][j] + x.d){
dist1[0][x.y] = dist1[0][j] + x.d;
}
}
}
for (int j = m - 1;j>=0;--j){
for (auto x:adj[k][j]){
if (x.x == k)
if (dist1[0][x.y] > dist1[0][j] + x.d){
dist1[0][x.y] = dist1[0][j] + x.d;
}
}
}
for (int j = 0;j<m;++j){
q.push({-dist1[0][j],{k,j}});
}
}
while(!q.empty()){
auto u = q.top();
dist2[u.second.first % block][u.second.second] = 1e9;
q.pop();
if (dist1[u.second.first % block][u.second.second] != -u.first)continue;
for (auto x:adj[u.second.first][u.second.second]){
dist2[x.x % block][x.y] = 1e9;
if (u.second.first - x.x > 0 || x.x > en)continue;
if (dist1[x.x % block][x.y] > -u.first + x.d){
dist1[x.x % block][x.y] = -u.first + x.d;
q.push({-dist1[x.x % block][x.y],{x.x,x.y}});
}
}
}
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[en % block][j];
//cout<<i<<" "<<en<<" "<<j<<" "<<dist3[i][j]<<'\n';
}
swap(dist1,dist2);
}
}
}
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;
}
}
int block = sqrt(n);
for (int i = 0;i<=block;++i){
for (int j = 0;j<m;++j){
dist1[i][j] = 1e9,dist2[i][j] = 1e9;
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<m;++j){
dist3[i][j] = 0;
}
}
for (int i = 0;i<m;++i){
for (int k = 0;k<n;k+=block){
int en = min(k + block - 1,n - 1);
int vv = en - k;
priority_queue<pair<int,pair<int,int>>>q;
for (int j = 0;j<block;++j){
for (int p = 0;p<m;++p){
dist1[j][p] = 1e9;
}
}
if (k == 0){
dist1[0][i] = 0;
q.push({0,{0,i}});
}
else{
for (int j = 0;j<m;++j){
for (auto x:rev_adj[k][j]){
if (x.y == j)
dist1[0][j] = dist3[i][j] + x.d;
}
//cout<<i<<" "<<k<<" "<<j<<" "<<dist1[0][j]<<" "<<dist3[i][j]<<'\n';
}
for (int j = 0;j<m;++j){
for (auto x:adj[k][j]){
if (x.x == k)
if (dist1[0][x.y] > dist1[0][j] + x.d){
dist1[0][x.y] = dist1[0][j] + x.d;
}
}
}
for (int j = m - 1;j>=0;--j){
for (auto x:adj[k][j]){
if (x.x == k)
if (dist1[0][x.y] > dist1[0][j] + x.d){
dist1[0][x.y] = dist1[0][j] + x.d;
}
}
}
for (int j = 0;j<m;++j){
q.push({-dist1[0][j],{k,j}});
}
}
while(!q.empty()){
auto u = q.top();
dist2[u.second.first % block][u.second.second] = 1e9;
q.pop();
if (dist1[u.second.first % block][u.second.second] != -u.first)continue;
for (auto x:adj[u.second.first][u.second.second]){
dist2[x.x % block][x.y] = 1e9;
if (u.second.first - x.x > 0 || x.x > en)continue;
if (dist1[x.x % block][x.y] > -u.first + x.d){
dist1[x.x % block][x.y] = -u.first + x.d;
q.push({-dist1[x.x % block][x.y],{x.x,x.y}});
}
}
}
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[en % block][j];
}
swap(dist1,dist2);
}
}
}
void changeV(int P, int Q, int W) {
for (auto &x:adj[P][Q]){
if (x.x == P + 1){
x.d = W;
}
}
int block = sqrt(n);
for (int i = 0;i<=block;++i){
for (int j = 0;j<m;++j){
dist1[i][j] = 1e9,dist2[i][j] = 1e9;
}
}
for (int i = 0;i<m;++i){
for (int j = 0;j<m;++j){
dist3[i][j] = 0;
}
}
for (int i = 0;i<m;++i){
for (int k = 0;k<n;k+=block){
int en = min(k + block - 1,n - 1);
int vv = en - k;
priority_queue<pair<int,pair<int,int>>>q;
for (int j = 0;j<block;++j){
for (int p = 0;p<m;++p){
dist1[j][p] = 1e9;
}
}
if (k == 0){
dist1[0][i] = 0;
q.push({0,{0,i}});
}
else{
for (int j = 0;j<m;++j){
for (auto x:rev_adj[k][j]){
if (x.y == j)
dist1[0][j] = dist3[i][j] + x.d;
}
}
for (int j = 0;j<m;++j){
for (auto x:adj[k][j]){
if (x.x == k)
if (dist1[0][x.y] > dist1[0][j] + x.d){
dist1[0][x.y] = dist1[0][j] + x.d;
}
}
}
for (int j = m - 1;j>=0;--j){
for (auto x:adj[k][j]){
if (x.x == k)
if (dist1[0][x.y] > dist1[0][j] + x.d){
dist1[0][x.y] = dist1[0][j] + x.d;
}
}
}
for (int j = 0;j<m;++j){
q.push({-dist1[0][j],{k,j}});
}
}
while(!q.empty()){
auto u = q.top();
dist2[u.second.first % block][u.second.second] = 1e9;
q.pop();
if (dist1[u.second.first % block][u.second.second] != -u.first)continue;
for (auto x:adj[u.second.first][u.second.second]){
dist2[x.x % block][x.y] = 1e9;
if (u.second.first - x.x > 0 || x.x > en)continue;
if (dist1[x.x % block][x.y] > -u.first + x.d){
dist1[x.x % block][x.y] = -u.first + x.d;
q.push({-dist1[x.x % block][x.y],{x.x,x.y}});
}
}
}
for (int j = 0;j<m;++j){
dist3[i][j] = dist1[en % block][j];
}
swap(dist1,dist2);
}
}
}
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;
| ^~~
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:43:11: warning: unused variable 'vv' [-Wunused-variable]
43 | int vv = en - k;
| ^~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:133:11: warning: unused variable 'vv' [-Wunused-variable]
133 | int vv = en - k;
| ^~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:217:11: warning: unused variable 'vv' [-Wunused-variable]
217 | int vv = en - k;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20016 ms |
12888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8028 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8024 KB |
Output is correct |
| 4 |
Correct |
109 ms |
10332 KB |
Output is correct |
| 5 |
Correct |
96 ms |
10332 KB |
Output is correct |
| 6 |
Correct |
75 ms |
10328 KB |
Output is correct |
| 7 |
Correct |
123 ms |
10328 KB |
Output is correct |
| 8 |
Correct |
76 ms |
10332 KB |
Output is correct |
| 9 |
Correct |
135 ms |
10392 KB |
Output is correct |
| 10 |
Correct |
77 ms |
10332 KB |
Output is correct |
| 11 |
Correct |
113 ms |
12708 KB |
Output is correct |
| 12 |
Correct |
79 ms |
8280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20025 ms |
9816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20007 ms |
17496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20028 ms |
11860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
20020 ms |
11868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
