oj.uz

답안 #1074359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074359 2024-08-25T10:03:27 Z 1ne 웜뱃 (IOI13_wombats) C++14
12 / 100
 20000 ms 17500 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;
		}
    }
    for (auto &x:rev_adj[P + 1][Q]){
		if (x.x == P){
			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:222:11: warning: unused variable 'vv' [-Wunused-variable]
  222 |       int vv = en - k;
      |           ^~

Subtask #1
0 / 9.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8028 KB Output is correct
2 Correct 6 ms 8028 KB Output is correct
3 Correct 5 ms 8024 KB Output is correct
4 Correct 106 ms 10332 KB Output is correct
5 Correct 105 ms 10388 KB Output is correct
6 Correct 80 ms 10328 KB Output is correct
7 Correct 73 ms 10332 KB Output is correct
8 Correct 76 ms 10332 KB Output is correct
9 Correct 73 ms 10332 KB Output is correct
10 Correct 70 ms 10332 KB Output is correct
11 Correct 120 ms 11360 KB Output is correct
12 Correct 75 ms 10332 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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