Submission #377829

#	Time	Username	Problem	Language	Result	Execution time	Memory
377829		kshitij_sodani	Patkice II (COCI21_patkice2)	C++14	110 / 110	894 ms	259232 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int n,m;
int it[2001][2001];
vector<pair<pair<int,int>,int>> adj[2001][2001];
int dist[2001][2001];
pair<int,int> ba[2001][2001];
char ans[2001][2001];
vector<int> xx={0,0,-1,1};
		vector<int> yy={1,-1,0,0};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	pair<int,int> st;
	pair<int,int> endd;
	
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		for(int j=0;j<m;j++){
			ans[i][j]=s[j];
			if(s[j]=='<'){
				if(j>0){
					adj[i][j].pb({{i,j-1},0});
				}
			}
			else if(s[j]=='>'){
				if(j+1<m){
					adj[i][j].pb({{i,j+1},0});
				}
			}
			else if(s[j]=='^'){
				if(i>0){
					adj[i][j].pb({{i-1,j},0});
				}
			}
			else if(s[j]=='v'){
				if(i+1<n){
					adj[i][j].pb({{i+1,j},0});
				}
			}
			else if(s[j]=='x'){
				endd={i,j};
			}
			else if(s[j]=='.'){

			}
			else{
				st={i,j};
			}
		}
	}
/*	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int cur=1;
			if(i==st.a and j==st.b){
				cur=0;
			}
			if(j>0){
				adj[i][j].pb({{i,j-1},cur});
			}
			if(j+1<m){
				adj[i][j].pb({{i,j+1},cur});
			}
			if(i>0){
				adj[i][j].pb({{i-1,j},cur});
			}
			if(i+1<n){
				adj[i][j].pb({{i+1,j},cur});
			}
		}
	}*/
	deque<pair<int,int>> ss;
	ss.pb(st);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			dist[i][j]=n*m;
		}
	}
	dist[st.a][st.b]=0;

	while(ss.size()){
		pair<int,int> no=ss.front();
		ss.pop_front();
		for(auto j:adj[no.a][no.b]){
			if(dist[j.a.a][j.a.b]>dist[no.a][no.b]+j.b){
				dist[j.a.a][j.a.b]=dist[no.a][no.b]+j.b;
				ba[j.a.a][j.a.b]={no.a,no.b};
				if(j.b==0){
					ss.push_front(j.a);
				}
				else{
					ss.pb(j.a);
				}
			}
		}
		for(int jj=0;jj<4;jj++){
			pair<pair<int,int>,int> j={{no.a+xx[jj],no.b+yy[jj]},1};
			if(j.a.a<0 or j.a.b<0 or j.a.a>=n or j.a.b>=m){
				continue;
			}
			if(no.a==st.a and no.b==st.b){
				j.b=0;
			}
			if(dist[j.a.a][j.a.b]>dist[no.a][no.b]+j.b){
				dist[j.a.a][j.a.b]=dist[no.a][no.b]+j.b;
				ba[j.a.a][j.a.b]={no.a,no.b};
				if(j.b==0){
					ss.push_front(j.a);
				}
				else{
					ss.pb(j.a);
				}
			}

		}

	}
	pair<int,int> cur;
	cur=endd;
	while(true){
		pair<int,int> cur2;
		cur2=cur;
		cur=ba[cur.a][cur.b];
		if(cur.a==st.a and cur.b==st.b){
			break;
		}
		if(cur.a==endd.a and cur.b==endd.b){
			continue;
		}
		if(cur.a+1==cur2.a){
			ans[cur.a][cur.b]='v';
		}
		if(cur.a-1==cur2.a){
			ans[cur.a][cur.b]='^';
		}
		if(cur.b-1==cur2.b){
			ans[cur.a][cur.b]='<';
		}

		if(cur.b+1==cur2.b){
			ans[cur.a][cur.b]='>';
		}


	}
	cout<<dist[endd.a][endd.b]<<endl;

	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<ans[i][j];
		}
		cout<<endl;
	}




	
 
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80