oj.uz

Submission #1074226

# Submission time Handle Problem Language Result Execution time Memory
1074226 2024-08-25T08:55:33 Z 1ne Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 17608 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 (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 413 ms 12376 KB Output is correct
2 Correct 391 ms 12376 KB Output is correct
3 Correct 428 ms 14136 KB Output is correct
4 Correct 431 ms 12380 KB Output is correct
5 Correct 414 ms 12380 KB Output is correct
6 Correct 6 ms 8024 KB Output is correct
7 Correct 4 ms 8028 KB Output is correct
8 Correct 4 ms 8028 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 4 ms 8028 KB Output is correct
3 Correct 4 ms 8128 KB Output is correct
4 Correct 25 ms 8280 KB Output is correct
5 Correct 17 ms 8284 KB Output is correct
6 Correct 18 ms 8284 KB Output is correct
7 Correct 20 ms 8284 KB Output is correct
8 Correct 20 ms 8368 KB Output is correct
9 Correct 18 ms 8284 KB Output is correct
10 Correct 22 ms 8284 KB Output is correct
11 Correct 57 ms 9268 KB Output is correct
12 Correct 20 ms 8364 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19308 ms 9560 KB Output is correct
2 Execution timed out 20024 ms 9632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 16824 KB Output is correct
2 Correct 1611 ms 16828 KB Output is correct
3 Correct 1066 ms 16728 KB Output is correct
4 Correct 1115 ms 17608 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18997 ms 9360 KB Output is correct
2 Execution timed out 20061 ms 9504 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

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