oj.uz

Submission #1074149

# Submission time Handle Problem Language Result Execution time Memory
1074149 2024-08-25T08:23:20 Z 1ne Wombats (IOI13_wombats) C++14
21 / 100
 20000 ms 166068 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
  int x,y,d;
};
vector<vector<vector<node>>>adj;
int dist1[200][500][200];
int dist2[200][500][200];
int dist3[200][200];
int n,m;
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));
    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]});
    		adj[i + 1][j].push_back({i,j,V[i][j]});
    	}
    }
    for (int i = 0;i<200;++i){
    	for (int j = 0;j<500;++j){
    		for (int k = 0;k<200;++k){
    			dist1[i][j][k] = 1e9;
    			dist2[i][j][k] = 1e9;
    			dist3[i][k] = 1e9;
    		}
    	}
    }
	for (int i = 0;i<C;++i){
		queue<pair<int,int>>q;
		q.push({0,i});
		dist1[i][0][i] = 0;
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:adj[u.first][u.second]){
				if (u.first - x.x > 0)continue;
				if (dist1[i][x.x][x.y] > dist1[i][u.first][u.second] + x.d){
					dist1[i][x.x][x.y] = dist1[i][u.first][u.second] + x.d;
					q.push({x.x,x.y});
				}	
			}
		}
	}
	for (int i = 0;i<C;++i){
		for (int j = 0;j<C;++j){
			dist3[i][j] = dist1[i][n - 1][j];
		}
	}	
	for (int i = 0;i<C;++i){
		queue<pair<int,int>>q;
		q.push({R - 1,i});
		dist2[i][R - 1][i] = 0;
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:adj[u.first][u.second]){
				if (u.first - x.x > 0)continue;
				if (dist2[i][x.x][x.y] > dist2[i][u.first][u.second] + x.d){
					dist2[i][x.x][x.y] = dist2[i][u.first][u.second] + x.d;
					q.push({x.x,x.y});
				}	
			}
		}
	}
}

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;
		}
	}
	for (int i = 0;i<200;++i){
    	for (int j = 0;j<500;++j){
    		for (int k = 0;k<200;++k){
    			dist1[i][j][k] = 1e9;
    			dist2[i][j][k] = 1e9;
    			dist3[i][k] = 1e9;
    		}
    	}
    }
	for (int i = 0;i<m;++i){
		queue<pair<int,int>>q;
		q.push({0,i});
		dist1[i][0][i] = 0;
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:adj[u.first][u.second]){
				if (u.first - x.x > 0)continue;
				if (dist1[i][x.x][x.y] > dist1[i][u.first][u.second] + x.d){
					dist1[i][x.x][x.y] = dist1[i][u.first][u.second] + x.d;
					q.push({x.x,x.y});
				}	
			}
		}
	}
	for (int i = 0;i<m;++i){
		for (int j = 0;j<m;++j){
			dist3[i][j] = dist1[i][n - 1][j];
		}
	}	
	for (int i = 0;i<m;++i){
		queue<pair<int,int>>q;
		q.push({n - 1,i});
		dist2[i][n - 1][i] = 0;
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:adj[u.first][u.second]){
				if (u.first - x.x > 0)continue;
				if (dist2[i][x.x][x.y] > dist2[i][u.first][u.second] + x.d){
					dist2[i][x.x][x.y] = dist2[i][u.first][u.second] + x.d;
					q.push({x.x,x.y});
				}	
			}
		}
	}	    
}

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:adj[P + 1][Q]){
		if (x.x == P){
			x.d = W;
		}
	}
	
	for (int i = 0;i<200;++i){
    	for (int j = 0;j<500;++j){
    		for (int k = 0;k<200;++k){
    			dist1[i][j][k] = 1e9;
    			dist2[i][j][k] = 1e9;
    			dist3[i][k] = 1e9;
    		}
    	}
    }
	for (int i = 0;i<m;++i){
		queue<pair<int,int>>q;
		q.push({0,i});
		dist1[i][0][i] = 0;
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:adj[u.first][u.second]){
				if (u.first - x.x > 0)continue;
				if (dist1[i][x.x][x.y] > dist1[i][u.first][u.second] + x.d){
					dist1[i][x.x][x.y] = dist1[i][u.first][u.second] + x.d;
					q.push({x.x,x.y});
				}	
			}
		}
	}
	for (int i = 0;i<m;++i){
		for (int j = 0;j<m;++j){
			dist3[i][j] = dist1[i][n - 1][j];
		}
	}	
	for (int i = 0;i<m;++i){
		queue<pair<int,int>>q;
		q.push({n - 1,i});
		dist2[i][n - 1][i] = 0;
		while(!q.empty()){
			auto u = q.front();
			q.pop();
			for (auto x:adj[u.first][u.second]){
				if (u.first - x.x > 0)continue;
				if (dist2[i][x.x][x.y] > dist2[i][u.first][u.second] + x.d){
					dist2[i][x.x][x.y] = dist2[i][u.first][u.second] + x.d;
					q.push({x.x,x.y});
				}	
			}
		}
	}
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11278 ms 161504 KB Output is correct
2 Correct 11178 ms 161516 KB Output is correct
3 Correct 11212 ms 164180 KB Output is correct
4 Correct 11233 ms 161508 KB Output is correct
5 Correct 11089 ms 161368 KB Output is correct
6 Correct 79 ms 158544 KB Output is correct
7 Correct 90 ms 158544 KB Output is correct
8 Correct 74 ms 158544 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 158412 KB Output is correct
2 Correct 84 ms 158476 KB Output is correct
3 Correct 81 ms 158496 KB Output is correct
4 Correct 81 ms 159232 KB Output is correct
5 Correct 78 ms 160592 KB Output is correct
6 Correct 101 ms 159056 KB Output is correct
7 Correct 86 ms 159208 KB Output is correct
8 Correct 83 ms 159040 KB Output is correct
9 Correct 106 ms 160604 KB Output is correct
10 Correct 88 ms 159228 KB Output is correct
11 Correct 134 ms 161572 KB Output is correct
12 Correct 84 ms 160600 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17355 ms 160204 KB Output is correct
2 Execution timed out 20084 ms 160204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20077 ms 166068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17480 ms 160208 KB Output is correct
2 Execution timed out 20067 ms 158232 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17332 ms 160208 KB Output is correct
2 Execution timed out 20065 ms 159972 KB Time limit exceeded
3 Halted 0 ms 0 KB -