oj.uz

답안 #1074363

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074363 2024-08-25T10:05:31 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;
			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<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;
			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<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;
			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:118:11: warning: unused variable 'vv' [-Wunused-variable]
  118 |       int vv = en - k;
      |           ^~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:192:11: warning: unused variable 'vv' [-Wunused-variable]
  192 |       int vv = en - k;
      |           ^~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 20032 ms 12888 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 4 ms 8028 KB Output is correct
4 Correct 74 ms 10332 KB Output is correct
5 Correct 72 ms 10332 KB Output is correct
6 Correct 73 ms 10328 KB Output is correct
7 Correct 72 ms 10328 KB Output is correct
8 Correct 70 ms 10388 KB Output is correct
9 Correct 75 ms 10384 KB Output is correct
10 Correct 68 ms 10328 KB Output is correct
11 Correct 111 ms 11156 KB Output is correct
12 Correct 73 ms 10328 KB Output is correct

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

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