Submission #447026

#	Time	Username	Problem	Language	Result	Execution time	Memory
447026		Jasiekstrz	Patkice II (COCI21_patkice2)	C++17	110 / 110	1686 ms	263572 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e3;
const int INF=1e9+7;
vector<pair<int,int>> edg={{-1,0},{1,0},{0,-1},{0,+1}};
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);
			}
		}
		for(auto [a,b]:edg)
		{
			int cc=1;
			a+=x;
			b+=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 / 30
• Subtask 2: 80 / 80