oj.uz

Submission #447024

# Submission time Handle Problem Language Result Execution time Memory
447024 2021-07-24T08:48:56 Z Jasiekstrz Patkice II (COCI21_patkice2) C++17
30 / 110
 1705 ms 524292 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e3;
const int INF=1e9+7;
vector<tuple<int,int,int>> e[N+10][N+10];
pair<int,int> p[N+10][N+10];
char c[N+10][N+10];
int d[N+10][N+10];
priority_queue<tuple<int,int,int>> pq;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	pair<int,int> s,f;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			e[i][j]={{i-1,j,1},{i+1,j,1},{i,j-1,1},{i,j+1,1}};
			if(c[i][j]=='o')
				s={i,j};
			if(c[i][j]=='x')
				f={i,j};
			if(c[i][j]=='<')
				e[i][j].emplace_back(i,j-1,0);
			if(c[i][j]=='>')
				e[i][j].emplace_back(i,j+1,0);
			if(c[i][j]=='^')
				e[i][j].emplace_back(i-1,j,0);
			if(c[i][j]=='v')
				e[i][j].emplace_back(i+1,j,0);
			d[i][j]=INF;
		}
	}
	pq.emplace(0,s.fi,s.se);
	d[s.fi][s.se]=0;
	while(!pq.empty())
	{
		auto [w,x,y]=pq.top();
		pq.pop();
		w=-w;
		if(d[x][y]!=w)
			continue;
		for(auto [a,b,cc]:e[x][y])
		{
			if(d[a][b]>w+cc)
			{
				d[a][b]=w+cc;
				p[a][b]={x,y};
				pq.emplace(-w-cc,a,b);
			}
		}
	}
	cout<<d[f.fi][f.se]-1<<"\n";
	for(auto i=f;p[i.fi][i.se]!=s;i=p[i.fi][i.se])
	{
		auto pp=p[i.fi][i.se];
		if(pp.fi<i.fi)
			c[pp.fi][pp.se]='v';
		if(pp.fi>i.fi)
			c[pp.fi][pp.se]='^';
		if(pp.se<i.se)
			c[pp.fi][pp.se]='>';
		if(pp.se>i.se)
			c[pp.fi][pp.se]='<';
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<c[i][j];
		cout<<"\n";
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 95176 KB Output is correct
2 Correct 52 ms 95248 KB Output is correct
3 Correct 51 ms 95268 KB Output is correct
4 Correct 51 ms 95384 KB Output is correct
5 Correct 54 ms 95188 KB Output is correct

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 95176 KB Output is correct
2 Correct 52 ms 95248 KB Output is correct
3 Correct 51 ms 95268 KB Output is correct
4 Correct 51 ms 95384 KB Output is correct
5 Correct 54 ms 95188 KB Output is correct
6 Correct 297 ms 157884 KB Output is correct
7 Correct 363 ms 169140 KB Output is correct
8 Correct 720 ms 250820 KB Output is correct
9 Correct 1397 ms 368280 KB Output is correct
10 Correct 1705 ms 458356 KB Output is correct
11 Runtime error 735 ms 524292 KB Execution killed with signal 9