oj.uz

답안 #1074355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074355 2024-08-25T10:01:56 Z 1ne 웜뱃 (IOI13_wombats) C++14
12 / 100
 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;
      |           ^~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20016 ms 12888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20025 ms 9816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20007 ms 17496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20028 ms 11860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20020 ms 11868 KB Time limit exceeded
2 Halted 0 ms 0 KB -