oj.uz

Submission #1074202

# Submission time Handle Problem Language Result Execution time Memory
1074202 2024-08-25T08:48:53 Z 1ne Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 18512 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;
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));
    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 403 ms 12636 KB Output is correct
2 Correct 433 ms 12632 KB Output is correct
3 Correct 435 ms 15276 KB Output is correct
4 Correct 418 ms 12880 KB Output is correct
5 Correct 403 ms 12556 KB Output is correct
6 Correct 4 ms 8280 KB Output is correct
7 Correct 4 ms 8176 KB Output is correct
8 Correct 4 ms 8024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 6 ms 8028 KB Output is correct
4 Correct 19 ms 10332 KB Output is correct
5 Correct 19 ms 10332 KB Output is correct
6 Correct 23 ms 10332 KB Output is correct
7 Correct 19 ms 10328 KB Output is correct
8 Correct 19 ms 10396 KB Output is correct
9 Correct 19 ms 10396 KB Output is correct
10 Correct 17 ms 10328 KB Output is correct
11 Correct 56 ms 12740 KB Output is correct
12 Correct 18 ms 10332 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19149 ms 11416 KB Output is correct
2 Execution timed out 20057 ms 11536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 17216 KB Output is correct
2 Correct 1750 ms 17204 KB Output is correct
3 Correct 1151 ms 17240 KB Output is correct
4 Correct 1383 ms 18512 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20000 ms 11408 KB Output is correct
2 Execution timed out 20033 ms 11712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19281 ms 11420 KB Output is correct
2 Execution timed out 20031 ms 11688 KB Time limit exceeded
3 Halted 0 ms 0 KB -