Submission #1074355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074355		1ne	Wombats (IOI13_wombats)	C++14	12 / 100	20028 ms	17496 KiB

wombats

#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 (stderr)

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;
      |           ^~

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24