oj.uz

Submission #897423

# Submission time Handle Problem Language Result Execution time Memory
897423 2024-01-03T05:10:10 Z Faisal_Saqib Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 25024 KB 
#include "wombats.h"
#include <iostream>
#include <set>
using namespace std;
int h[5000][200];
int v[5000][200];
long long dist[5000][200];
int n,m;
long long ans=0;
bool Valid(int i,int j){
	return (0<=i and i<n and 0<=j and j<m);
}
void init(int r, int c, int H[5000][200], int V[5000][200])
{
	n=r;
	m=c;
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<(c-1);j++)
		{
			ans+=H[i][j];
			h[i][j]=H[i][j];
		}
	}
	for(int i=0;i<(r-1);i++)
	{
		for(int j=0;j<c;j++)
		{
			ans+=V[i][j];
			v[i][j]=V[i][j];
		}
	}
}
void changeH(int p, int q, int w)
{
	h[p][q]=w;
}
void changeV(int p, int q, int w)
{
	v[p][q]=w;
}
int escape(int V1, int V2)
{
	if(m==1)
		return ans;
	set<pair<long long,pair<int,int>>> sp;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			dist[i][j]=1e18;
		}
	}
	dist[0][V1]=0;
	sp.insert({0,{0,V1}});
	// cout<<"ST "<<0<<' '<<V1<<endl;
	while(sp.size())
	{
		auto f=*begin(sp);
		// cout<<"Hola "<<f.second.first<<' '<<f.second.second<<' '<<f.first<<endl;;
		if(f.second.first==(n-1) and f.second.second==V2)
			return f.first;
		sp.erase(begin(sp));
		if(Valid(f.second.first+1,f.second.second) and dist[f.second.first+1][f.second.second]>(f.first+v[f.second.first][f.second.second]))
		{
			sp.erase({dist[f.second.first+1][f.second.second],{f.second.first+1,f.second.second}});
			dist[f.second.first+1][f.second.second]=(f.first+v[f.second.first][f.second.second]);
			sp.insert({dist[f.second.first+1][f.second.second],{f.second.first+1,f.second.second}});
		}
		if(Valid(f.second.first,f.second.second+1) and dist[f.second.first][f.second.second+1]>(f.first+h[f.second.first][f.second.second]))
		{
			sp.erase({dist[f.second.first][f.second.second+1],{f.second.first,f.second.second+1}});
			dist[f.second.first][f.second.second+1]=(f.first+h[f.second.first][f.second.second]);
			sp.insert({dist[f.second.first][f.second.second+1],{f.second.first,f.second.second+1}});
		}

		// if(Valid(f.second.first-1,f.second.second) and dist[f.second.first-1][f.second.second]>(f.first+v[f.second.first-1][f.second.second]))
		// {
		// 	sp.erase({dist[f.second.first-1][f.second.second],{f.second.first-1,f.second.second}});
		// 	dist[f.second.first-1][f.second.second]=(f.first+v[f.second.first-1][f.second.second]);
		// 	sp.insert({dist[f.second.first-1][f.second.second],{f.second.first-1,f.second.second}});
		// }
		if(Valid(f.second.first,f.second.second-1) and dist[f.second.first][f.second.second-1]>(f.first+h[f.second.first][f.second.second-1]))
		{
			// cout<<"For now "<<v[f.second.first][f.second.second-1]<<endl;
			sp.erase({dist[f.second.first][f.second.second-1],{f.second.first,f.second.second-1}});
			dist[f.second.first][f.second.second-1]=(f.first+h[f.second.first][f.second.second-1]);
			sp.insert({dist[f.second.first][f.second.second-1],{f.second.first,f.second.second-1}});
		}
	}
	return 0;
}

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Incorrect 2 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 20 ms 8540 KB Output is correct
5 Correct 12 ms 8540 KB Output is correct
6 Correct 11 ms 8672 KB Output is correct
7 Correct 20 ms 8676 KB Output is correct
8 Correct 19 ms 8540 KB Output is correct
9 Correct 23 ms 8684 KB Output is correct
10 Correct 20 ms 8536 KB Output is correct
11 Correct 10587 ms 11732 KB Output is correct
12 Correct 24 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 8792 KB Output is correct
2 Correct 203 ms 8812 KB Output is correct
3 Correct 225 ms 8796 KB Output is correct
4 Correct 172 ms 8796 KB Output is correct
5 Correct 172 ms 8792 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 196 ms 8804 KB Output is correct
10 Correct 1 ms 8732 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 23972 KB Output is correct
2 Correct 609 ms 23900 KB Output is correct
3 Correct 593 ms 23900 KB Output is correct
4 Execution timed out 20047 ms 24424 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 8796 KB Output is correct
2 Correct 202 ms 8796 KB Output is correct
3 Correct 174 ms 8800 KB Output is correct
4 Correct 173 ms 8800 KB Output is correct
5 Correct 172 ms 8796 KB Output is correct
6 Correct 588 ms 24148 KB Output is correct
7 Correct 643 ms 23900 KB Output is correct
8 Correct 583 ms 23976 KB Output is correct
9 Execution timed out 20013 ms 24900 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 8800 KB Output is correct
2 Correct 201 ms 8792 KB Output is correct
3 Correct 179 ms 8796 KB Output is correct
4 Correct 179 ms 8804 KB Output is correct
5 Correct 172 ms 8792 KB Output is correct
6 Correct 592 ms 23980 KB Output is correct
7 Correct 600 ms 23896 KB Output is correct
8 Correct 596 ms 23968 KB Output is correct
9 Execution timed out 20091 ms 25024 KB Time limit exceeded
10 Halted 0 ms 0 KB -