oj.uz

Submission #447026

# Submission time Handle Problem Language Result Execution time Memory
447026 2021-07-24T08:52:38 Z Jasiekstrz Patkice II (COCI21_patkice2) C++17
110 / 110
 1686 ms 263572 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 95168 KB Output is correct
2 Correct 63 ms 95196 KB Output is correct
3 Correct 62 ms 95324 KB Output is correct
4 Correct 63 ms 95304 KB Output is correct
5 Correct 63 ms 95172 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 95168 KB Output is correct
2 Correct 63 ms 95196 KB Output is correct
3 Correct 62 ms 95324 KB Output is correct
4 Correct 63 ms 95304 KB Output is correct
5 Correct 63 ms 95172 KB Output is correct
6 Correct 247 ms 120404 KB Output is correct
7 Correct 280 ms 127912 KB Output is correct
8 Correct 530 ms 154112 KB Output is correct
9 Correct 988 ms 201248 KB Output is correct
10 Correct 1255 ms 221728 KB Output is correct
11 Correct 1686 ms 263572 KB Output is correct