oj.uz

답안 #897436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897436 2024-01-03T05:39:01 Z Faisal_Saqib 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 20068 KB 
#include "wombats.h"
#include <iostream>
#include <set>
using namespace std;
int h[5000][200];
int v[5000][200];
int dist[5000][200];
int dist_level[2][5000][2];
int n,m;
int 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<int,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<int,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;
      |      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:75:27: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   75 |      dist_level[st][i][j]=1e18;
      |                           ^~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:91:27: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   91 |      dist_level[st][i][j]=1e18;
      |                           ^~~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:104:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
  104 |    dist[i][j]=1e18;
      |               ^~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 57 ms 14340 KB Output is correct
4 Correct 3 ms 12888 KB Output is correct
5 Correct 2 ms 12892 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

# 결과 실행 시간 메모리 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 19 ms 8540 KB Output is correct
5 Correct 12 ms 8664 KB Output is correct
6 Correct 11 ms 8540 KB Output is correct
7 Correct 26 ms 8644 KB Output is correct
8 Correct 21 ms 8672 KB Output is correct
9 Correct 22 ms 8540 KB Output is correct
10 Correct 20 ms 8540 KB Output is correct
11 Correct 10396 ms 9720 KB Output is correct
12 Correct 23 ms 8536 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 8536 KB Output is correct
2 Correct 197 ms 8716 KB Output is correct
3 Correct 169 ms 8540 KB Output is correct
4 Correct 169 ms 8724 KB Output is correct
5 Correct 167 ms 8540 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 4444 KB Output is correct
9 Correct 189 ms 8740 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 581 ms 18012 KB Output is correct
2 Correct 594 ms 18012 KB Output is correct
3 Correct 577 ms 18012 KB Output is correct
4 Correct 609 ms 18808 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 8720 KB Output is correct
2 Correct 200 ms 8716 KB Output is correct
3 Correct 169 ms 8720 KB Output is correct
4 Correct 169 ms 8728 KB Output is correct
5 Correct 171 ms 8720 KB Output is correct
6 Correct 577 ms 18012 KB Output is correct
7 Correct 591 ms 18016 KB Output is correct
8 Correct 580 ms 18012 KB Output is correct
9 Correct 609 ms 19052 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 57 ms 14456 KB Output is correct
13 Correct 2 ms 12892 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 19 ms 8536 KB Output is correct
19 Correct 12 ms 8540 KB Output is correct
20 Correct 11 ms 8540 KB Output is correct
21 Correct 23 ms 8536 KB Output is correct
22 Correct 18 ms 8668 KB Output is correct
23 Correct 22 ms 8540 KB Output is correct
24 Correct 20 ms 8540 KB Output is correct
25 Correct 10337 ms 9652 KB Output is correct
26 Correct 25 ms 8540 KB Output is correct
27 Correct 208 ms 8728 KB Output is correct
28 Execution timed out 20031 ms 20068 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 167 ms 8716 KB Output is correct
2 Correct 197 ms 8540 KB Output is correct
3 Correct 182 ms 8792 KB Output is correct
4 Correct 169 ms 8536 KB Output is correct
5 Correct 168 ms 8536 KB Output is correct
6 Correct 580 ms 18016 KB Output is correct
7 Correct 598 ms 18012 KB Output is correct
8 Correct 580 ms 18016 KB Output is correct
9 Correct 601 ms 18752 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 63 ms 14720 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 721 ms 20060 KB Output is correct
16 Execution timed out 20092 ms 20048 KB Time limit exceeded
17 Halted 0 ms 0 KB -