oj.uz

Submission #897424

# Submission time Handle Problem Language Result Execution time Memory
897424 2024-01-03T05:12:11 Z Faisal_Saqib Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 24648 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 109 ms 19064 KB Output is correct
2 Correct 102 ms 19060 KB Output is correct
3 Execution timed out 20010 ms 20864 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 21 ms 8668 KB Output is correct
5 Correct 12 ms 8536 KB Output is correct
6 Correct 11 ms 8664 KB Output is correct
7 Correct 19 ms 8668 KB Output is correct
8 Correct 19 ms 8676 KB Output is correct
9 Correct 22 ms 8540 KB Output is correct
10 Correct 21 ms 8540 KB Output is correct
11 Correct 10601 ms 9660 KB Output is correct
12 Correct 25 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 8724 KB Output is correct
2 Correct 201 ms 8716 KB Output is correct
3 Correct 173 ms 8540 KB Output is correct
4 Correct 173 ms 8536 KB Output is correct
5 Correct 170 ms 8540 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 192 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 24156 KB Output is correct
2 Correct 621 ms 23904 KB Output is correct
3 Correct 616 ms 23900 KB Output is correct
4 Execution timed out 20016 ms 24640 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 8540 KB Output is correct
2 Correct 202 ms 8716 KB Output is correct
3 Correct 176 ms 8716 KB Output is correct
4 Correct 174 ms 8724 KB Output is correct
5 Correct 173 ms 8536 KB Output is correct
6 Correct 613 ms 23900 KB Output is correct
7 Correct 626 ms 23900 KB Output is correct
8 Correct 628 ms 24148 KB Output is correct
9 Execution timed out 20008 ms 24648 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 8540 KB Output is correct
2 Correct 207 ms 8788 KB Output is correct
3 Correct 176 ms 8536 KB Output is correct
4 Correct 174 ms 8540 KB Output is correct
5 Correct 174 ms 8720 KB Output is correct
6 Correct 593 ms 23900 KB Output is correct
7 Correct 627 ms 24152 KB Output is correct
8 Correct 630 ms 24148 KB Output is correct
9 Execution timed out 20019 ms 24212 KB Time limit exceeded
10 Halted 0 ms 0 KB -