oj.uz

Submission #1074187

# Submission time Handle Problem Language Result Execution time Memory
1074187 2024-08-25T08:41:14 Z 1ne Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 108440 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;
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<m;++i){
		vector<vector<int>>dist1(n,vector<int>(m,1e9));
		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();
			if (dist1[u.second.first][u.second.second] != -u.first)continue;
			for (auto x:adj[u.second.first][u.second.second]){
				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];
		}
	}	
}

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){
		vector<vector<int>>dist1(n,vector<int>(m,1e9));
		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();
			if (dist1[u.second.first][u.second.second] != -u.first)continue;
			for (auto x:adj[u.second.first][u.second.second]){
				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];
		}
	}	    
}

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){
		vector<vector<int>>dist1(n,vector<int>(m,1e9));
		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();
			if (dist1[u.second.first][u.second.second] != -u.first)continue;
			for (auto x:adj[u.second.first][u.second.second]){
				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];
		}
	}
}

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 125 ms 5060 KB Output is correct
2 Correct 120 ms 5056 KB Output is correct
3 Correct 158 ms 6444 KB Output is correct
4 Correct 120 ms 5060 KB Output is correct
5 Correct 126 ms 5060 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 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 2392 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 45 ms 1664 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11659 ms 1624 KB Output is correct
2 Correct 17354 ms 3792 KB Output is correct
3 Correct 12256 ms 1584 KB Output is correct
4 Correct 12176 ms 3556 KB Output is correct
5 Correct 11602 ms 1368 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 20091 ms 3668 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 9656 KB Output is correct
2 Correct 955 ms 9564 KB Output is correct
3 Correct 485 ms 9564 KB Output is correct
4 Correct 487 ms 10872 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11600 ms 3616 KB Output is correct
2 Correct 16770 ms 3808 KB Output is correct
3 Correct 11967 ms 3632 KB Output is correct
4 Correct 11664 ms 3624 KB Output is correct
5 Correct 11554 ms 3624 KB Output is correct
6 Correct 467 ms 9564 KB Output is correct
7 Correct 1016 ms 9640 KB Output is correct
8 Correct 466 ms 9656 KB Output is correct
9 Correct 494 ms 11020 KB Output is correct
10 Correct 122 ms 5056 KB Output is correct
11 Correct 121 ms 5092 KB Output is correct
12 Correct 165 ms 7808 KB Output is correct
13 Correct 121 ms 5088 KB Output is correct
14 Correct 126 ms 5088 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 600 KB Output is correct
18 Correct 2 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Correct 1 ms 2496 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 41 ms 4760 KB Output is correct
26 Correct 1 ms 2392 KB Output is correct
27 Execution timed out 20034 ms 3856 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11888 ms 3620 KB Output is correct
2 Correct 16475 ms 4008 KB Output is correct
3 Correct 11724 ms 3420 KB Output is correct
4 Correct 11836 ms 3632 KB Output is correct
5 Correct 11457 ms 3620 KB Output is correct
6 Correct 500 ms 9564 KB Output is correct
7 Correct 954 ms 9560 KB Output is correct
8 Correct 475 ms 9564 KB Output is correct
9 Correct 504 ms 10836 KB Output is correct
10 Correct 120 ms 5060 KB Output is correct
11 Correct 131 ms 5092 KB Output is correct
12 Correct 157 ms 7656 KB Output is correct
13 Correct 137 ms 5092 KB Output is correct
14 Correct 136 ms 5060 KB Output is correct
15 Execution timed out 20041 ms 108440 KB Time limit exceeded
16 Halted 0 ms 0 KB -