oj.uz

Submission #1074208

# Submission time Handle Problem Language Result Execution time Memory
1074208 2024-08-25T08:51:37 Z 1ne Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 17932 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]){
				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]){
				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]){
				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 395 ms 12380 KB Output is correct
2 Correct 400 ms 12376 KB Output is correct
3 Correct 438 ms 14160 KB Output is correct
4 Correct 394 ms 12376 KB Output is correct
5 Correct 409 ms 12380 KB Output is correct
6 Correct 4 ms 8028 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 3 ms 8024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8024 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 20 ms 10160 KB Output is correct
5 Correct 20 ms 10392 KB Output is correct
6 Correct 19 ms 10388 KB Output is correct
7 Correct 19 ms 10404 KB Output is correct
8 Correct 18 ms 10328 KB Output is correct
9 Correct 19 ms 10332 KB Output is correct
10 Correct 19 ms 10332 KB Output is correct
11 Correct 59 ms 11344 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 19433 ms 11336 KB Output is correct
2 Execution timed out 20044 ms 11472 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 16988 KB Output is correct
2 Correct 1557 ms 17232 KB Output is correct
3 Correct 1060 ms 16988 KB Output is correct
4 Correct 1105 ms 17932 KB Output is correct

Subtask #5
0 / 21.0

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

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 19562 ms 11340 KB Output is correct
2 Execution timed out 20087 ms 11492 KB Time limit exceeded
3 Halted 0 ms 0 KB -