oj.uz

Submission #1074212

# Submission time Handle Problem Language Result Execution time Memory
1074212 2024-08-25T08:52:40 Z 1ne Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 102832 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
  int x,y,d;
};
vector<vector<vector<node>>>adj;
int dist3[200][200];
int n,m;
vector<vector<int>>dist1,dist2;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    n = R,m = C;
    dist1.resize(R,vector<int>(C));
    dist2.resize(R,vector<int>(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<n;++i){
    	for (int j = 0;j<m;++j){
    		dist1[i][j] = 1e9,dist2[i][j] = 1e9;
    	}
    }	
    for (int i = 0;i<m;++i){
		priority_queue<pair<int,pair<int,int>>>q;
		q.push({0,{0,i}});
		dist1[0][i] = 0;
		while(!q.empty()){
			auto u = q.top();
			dist2[u.second.first][u.second.second] = 1e9;
			q.pop();
			if (dist1[u.second.first][u.second.second] != -u.first)continue;
			for (auto x:adj[u.second.first][u.second.second]){
				dist2[x.x][x.y] = 1e9;
				if (u.second.first - x.x > 0)continue;
				if (dist1[x.x][x.y] > -u.first + x.d){
					dist1[x.x][x.y] = -u.first + x.d;
					q.push({-dist1[x.x][x.y],{x.x,x.y}});
				}	
			}
		}
		for (int j = 0;j<m;++j){
			dist3[i][j] = dist1[n - 1][j];
		}
		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;
		}
	}
	for (int i = 0;i<m;++i){
		priority_queue<pair<int,pair<int,int>>>q;
		q.push({0,{0,i}});
		dist1[0][i] = 0;
		while(!q.empty()){
			auto u = q.top();
			q.pop();
			dist2[u.second.first][u.second.second] = 1e9;
			if (dist1[u.second.first][u.second.second] != -u.first)continue;
			for (auto x:adj[u.second.first][u.second.second]){
				dist2[x.x][x.y] = 1e9;
				if (u.second.first - x.x > 0)continue;
				if (dist1[x.x][x.y] > -u.first + x.d){
					dist1[x.x][x.y] = -u.first + x.d;
					q.push({-dist1[x.x][x.y],{x.x,x.y}});
				}	
			}
		}
		for (int j = 0;j<m;++j){
			dist3[i][j] = dist1[n - 1][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:adj[P + 1][Q]){
		if (x.x == P){
			x.d = W;
		}
	}
	
	for (int i = 0;i<m;++i){
		priority_queue<pair<int,pair<int,int>>>q;
		q.push({0,{0,i}});
		dist1[0][i] = 0;
		while(!q.empty()){
			auto u = q.top();
			q.pop();
			dist2[u.second.first][u.second.second] = 1e9;
			if (dist1[u.second.first][u.second.second] != -u.first)continue;
			for (auto x:adj[u.second.first][u.second.second]){
				dist2[x.x][x.y] = 1e9;
				if (u.second.first - x.x > 0)continue;
				if (dist1[x.x][x.y] > -u.first + x.d){
					dist1[x.x][x.y] = -u.first + x.d;
					q.push({-dist1[x.x][x.y],{x.x,x.y}});
				}	
			}
		}
		for (int j = 0;j<m;++j){
			dist3[i][j] = dist1[n - 1][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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5212 KB Output is correct
2 Correct 50 ms 5212 KB Output is correct
3 Correct 107 ms 6736 KB Output is correct
4 Correct 60 ms 5208 KB Output is correct
5 Correct 51 ms 5312 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 548 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 44 ms 1520 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12501 ms 1640 KB Output is correct
2 Correct 17464 ms 1788 KB Output is correct
3 Correct 12715 ms 1716 KB Output is correct
4 Correct 12734 ms 1720 KB Output is correct
5 Correct 12668 ms 1724 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 20065 ms 3704 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 9816 KB Output is correct
2 Correct 898 ms 9816 KB Output is correct
3 Correct 341 ms 9820 KB Output is correct
4 Correct 356 ms 10492 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12920 ms 3600 KB Output is correct
2 Correct 17614 ms 3824 KB Output is correct
3 Correct 12463 ms 3684 KB Output is correct
4 Correct 12292 ms 3628 KB Output is correct
5 Correct 12482 ms 3680 KB Output is correct
6 Correct 338 ms 9820 KB Output is correct
7 Correct 834 ms 9920 KB Output is correct
8 Correct 335 ms 9932 KB Output is correct
9 Correct 362 ms 11088 KB Output is correct
10 Correct 50 ms 5212 KB Output is correct
11 Correct 49 ms 5212 KB Output is correct
12 Correct 88 ms 8004 KB Output is correct
13 Correct 49 ms 5600 KB Output is correct
14 Correct 52 ms 5212 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 38 ms 4688 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Execution timed out 20008 ms 3700 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12629 ms 3604 KB Output is correct
2 Correct 17694 ms 3952 KB Output is correct
3 Correct 12638 ms 3600 KB Output is correct
4 Correct 12441 ms 3564 KB Output is correct
5 Correct 12058 ms 3608 KB Output is correct
6 Correct 355 ms 9860 KB Output is correct
7 Correct 845 ms 10068 KB Output is correct
8 Correct 337 ms 9816 KB Output is correct
9 Correct 363 ms 10480 KB Output is correct
10 Correct 51 ms 5212 KB Output is correct
11 Correct 50 ms 5208 KB Output is correct
12 Correct 88 ms 6740 KB Output is correct
13 Correct 59 ms 5460 KB Output is correct
14 Correct 50 ms 5212 KB Output is correct
15 Execution timed out 20028 ms 102832 KB Time limit exceeded
16 Halted 0 ms 0 KB -