oj.uz

Submission #897435

# Submission time Handle Problem Language Result Execution time Memory
897435 2024-01-03T05:37:06 Z Faisal_Saqib Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 33632 KB 
#include "wombats.h"
#include <iostream>
#include <set>
using namespace std;
int h[5000][200];
int v[5000][200];
long long dist[5000][200];
long long dist_level[2][5000][2];
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 khatam(int st)
{
	set<pair<long long,pair<int,int>>> sp;
	dist_level[st][0][st]=0;
	sp.insert({0,{0,st}});
	while(sp.size())
	{
		auto f=*begin(sp);
		sp.erase(begin(sp));
		if(Valid(f.second.first+1,f.second.second) and dist_level[st][f.second.first+1][f.second.second]>(f.first+v[f.second.first][f.second.second]))
		{
			sp.erase({dist_level[st][f.second.first+1][f.second.second],{f.second.first+1,f.second.second}});
			dist_level[st][f.second.first+1][f.second.second]=(f.first+v[f.second.first][f.second.second]);
			sp.insert({dist_level[st][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_level[st][f.second.first][f.second.second+1]>(f.first+h[f.second.first][f.second.second]))
		{
			sp.erase({dist_level[st][f.second.first][f.second.second+1],{f.second.first,f.second.second+1}});
			dist_level[st][f.second.first][f.second.second+1]=(f.first+h[f.second.first][f.second.second]);
			sp.insert({dist_level[st][f.second.first][f.second.second+1],{f.second.first,f.second.second+1}});
		}
		if(Valid(f.second.first,f.second.second-1) and dist_level[st][f.second.first][f.second.second-1]>(f.first+h[f.second.first][f.second.second-1]))
		{
			sp.erase({dist_level[st][f.second.first][f.second.second-1],{f.second.first,f.second.second-1}});
			dist_level[st][f.second.first][f.second.second-1]=(f.first+h[f.second.first][f.second.second-1]);
			sp.insert({dist_level[st][f.second.first][f.second.second-1],{f.second.first,f.second.second-1}});
		}
	}
}
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)
{
	ans-=h[p][q];
	ans+=w;
	h[p][q]=w;
	if(m==2)
	{
		for(int st=0;st<m;st++)
		{
			for(int i=0;i<n;i++)
				for(int j=0;j<m;j++)
					dist_level[st][i][j]=1e18;
			khatam(st);
		}
	}
}
void changeV(int p, int q, int w)
{
	ans-=v[p][q];
	ans+=w;
	v[p][q]=w;
	if(m==2)
	{
		for(int st=0;st<m;st++)
		{
			for(int i=0;i<n;i++)
				for(int j=0;j<m;j++)
					dist_level[st][i][j]=1e18;
			khatam(st);
		}
	}
}
int escape(int V1, int V2)
{
	if(m==1)
		return ans;
	else if(m==2)
		return dist_level[V1][n-1][V2];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			dist[i][j]=1e18;
	set<pair<long long,pair<int,int>>> sp;
	dist[0][V1]=0;
	sp.insert({0,{0,V1}});
	while(sp.size())
	{
		auto f=*begin(sp);
		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,f.second.second-1) and dist[f.second.first][f.second.second-1]>(f.first+h[f.second.first][f.second.second-1]))
		{
			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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 61 ms 15028 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12936 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

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 8792 KB Output is correct
6 Correct 12 ms 8668 KB Output is correct
7 Correct 19 ms 8540 KB Output is correct
8 Correct 18 ms 8540 KB Output is correct
9 Correct 22 ms 8668 KB Output is correct
10 Correct 20 ms 8540 KB Output is correct
11 Correct 10503 ms 10000 KB Output is correct
12 Correct 28 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 8716 KB Output is correct
2 Correct 207 ms 8716 KB Output is correct
3 Correct 176 ms 8784 KB Output is correct
4 Correct 172 ms 8736 KB Output is correct
5 Correct 169 ms 8720 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 199 ms 8744 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 17908 KB Output is correct
2 Correct 621 ms 17896 KB Output is correct
3 Correct 612 ms 17896 KB Output is correct
4 Correct 631 ms 18920 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 8716 KB Output is correct
2 Correct 213 ms 8536 KB Output is correct
3 Correct 181 ms 8696 KB Output is correct
4 Correct 174 ms 8540 KB Output is correct
5 Correct 181 ms 8724 KB Output is correct
6 Correct 609 ms 17896 KB Output is correct
7 Correct 644 ms 17896 KB Output is correct
8 Correct 596 ms 17900 KB Output is correct
9 Correct 636 ms 18708 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 55 ms 15696 KB Output is correct
13 Correct 2 ms 12888 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 20 ms 8536 KB Output is correct
19 Correct 14 ms 8540 KB Output is correct
20 Correct 11 ms 8540 KB Output is correct
21 Correct 19 ms 8672 KB Output is correct
22 Correct 19 ms 8652 KB Output is correct
23 Correct 22 ms 8536 KB Output is correct
24 Correct 20 ms 8540 KB Output is correct
25 Correct 10629 ms 11488 KB Output is correct
26 Correct 24 ms 8536 KB Output is correct
27 Correct 191 ms 8792 KB Output is correct
28 Execution timed out 20101 ms 27612 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 8784 KB Output is correct
2 Correct 205 ms 8540 KB Output is correct
3 Correct 174 ms 8540 KB Output is correct
4 Correct 175 ms 8724 KB Output is correct
5 Correct 170 ms 8792 KB Output is correct
6 Correct 593 ms 18152 KB Output is correct
7 Correct 687 ms 17900 KB Output is correct
8 Correct 628 ms 17900 KB Output is correct
9 Correct 625 ms 18916 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 69 ms 15528 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 698 ms 33632 KB Output is correct
16 Execution timed out 20048 ms 31828 KB Time limit exceeded
17 Halted 0 ms 0 KB -