oj.uz

Submission #385482

# Submission time Handle Problem Language Result Execution time Memory
385482 2021-04-04T13:18:12 Z ogibogi2004 Robots (APIO13_robots) C++14
60 / 100
 1263 ms 163844 KB 
#include<bits/stdc++.h>
using namespace std;
#define ends dfdsfdsf
#define ll long long
const ll INF=1e12;
pair<pair<ll,ll>,ll> nxt[512][512][4];
vector<pair<pair<ll,ll>,ll> >g[512][512][4];
vector<pair<ll,ll> >g1[512][512];
char table[512][512];
ll r,n,m;
vector<pair<pair<ll,ll>,ll> >ends;
pair<pair<ll,ll>,ll> actual_nxt[512][512][4];
bool not_valid(pair<ll,ll> p)
{
	ll x=p.first,y=p.second;
	if(x<1||y<1||x>n||y>m)return 1;
	return table[x][y]=='x';
}
ll dp[10][10][512][512];
pair<ll,ll> where[10];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>r>>m>>n;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			cin>>table[i][j];
			if(isdigit(table[i][j]))
			{
				where[table[i][j]-'0']={i,j};
			}
		}
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			if(table[i][j]=='x')continue;
			if(table[i][j]=='A')
			{
				nxt[i][j][0]={{i,j-1},3};
				nxt[i][j][1]={{i-1,j},0};
				nxt[i][j][2]={{i,j+1},1};
				nxt[i][j][3]={{i+1,j},2};
			}
			else if(table[i][j]=='C')
			{
				nxt[i][j][0]={{i,j+1},1};
				nxt[i][j][1]={{i+1,j},2};
				nxt[i][j][2]={{i,j-1},3};
				nxt[i][j][3]={{i-1,j},0};
			}
			else
			{
				nxt[i][j][0]={{i-1,j},0};
				nxt[i][j][1]={{i,j+1},1};
				nxt[i][j][2]={{i+1,j},2};
				nxt[i][j][3]={{i,j-1},3};
			}
			for(ll l=0;l<4;l++)
			{
				if(not_valid(nxt[i][j][l].first))
				{
					ends.push_back({{i,j},l});
				}
				g[nxt[i][j][l].first.first][nxt[i][j][l].first.second][nxt[i][j][l].second].push_back({{i,j},l});
			}
		}
	}
	queue<pair<pair<ll,ll>,ll> >q;
	for(auto xd:ends)
	{
		q.push(xd);
		actual_nxt[xd.first.first][xd.first.second][xd.second]=xd;
	}
	while(!q.empty())
	{
		auto u=q.front();
		q.pop();
		for(auto xd:g[u.first.first][u.first.second][u.second])
		{
			actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second];
			q.push(xd);
		}
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			for(ll l=0;l<4;l++)
			{
				ll x,y,z;
				x=actual_nxt[i][j][l].first.first;
				y=actual_nxt[i][j][l].first.second;
				z=actual_nxt[i][j][l].second;
				if(x==i&&y==j&&z==l)continue;
				g1[i][j].push_back({x,y});
			}
		}
	}
	for(ll r1=1;r1<=r;r1++)
	{
		for(ll r2=1;r2<=r;r2++)
		{
			for(ll i1=1;i1<=n;i1++)
			{
				for(ll i2=1;i2<=m;i2++)
				{
					dp[r1][r2][i1][i2]=INF;
				}
			}
		}
	}
	for(ll i=1;i<=r;i++)
	{
		ll x,y;
		x=where[i].first;
		y=where[i].second;
		queue<pair<ll,ll> >q;
		q.push({x,y});
		dp[i][i][x][y]=0;
		while(!q.empty())
		{
			tie(x,y)=q.front();
			q.pop();
			for(auto xd:g1[x][y])
			{
				if(dp[i][i][xd.first][xd.second]>dp[i][i][x][y]+1)
				{
					dp[i][i][xd.first][xd.second]=dp[i][i][x][y]+1;
					q.push(xd);
				}
			}
		}
	}
	for(ll len=2;len<=r;len++)
	{
		for(ll r1=1;r1+len-1<=r;r1++)
		{
			ll r2=r1+len-1;
			for(ll mid=r1;mid<r2;mid++)
			{
				for(ll i=1;i<=n;i++)
				{
					for(ll j=1;j<=m;j++)
					{
						dp[r1][r2][i][j]=min(dp[r1][r2][i][j],dp[r1][mid][i][j]+dp[mid+1][r2][i][j]);
					}
				}
			}
			priority_queue<pair<ll,pair<ll,ll> > >pq;
			for(ll i=1;i<=n;i++)
			{
				for(ll j=1;j<=m;j++)
				{
					pq.push({-dp[r1][r2][i][j],{i,j}});
				}
			}
			while(!pq.empty())
			{
				ll x,y;
				ll t;
				t=pq.top().first;
				tie(x,y)=pq.top().second;
				pq.pop();
				if(t!=-dp[r1][r2][x][y])continue;
				for(auto xd:g1[x][y])
				{
					if(dp[r1][r2][x][y]+1<dp[r1][r2][xd.first][xd.second])
					{
						dp[r1][r2][xd.first][xd.second]=dp[r1][r2][x][y]+1;
						pq.push({-dp[r1][r2][xd.first][xd.second],{xd}});
					}
				}
			}
		}
	}
	/*for(ll i1=1;i1<=r;i1++)
	{
		for(ll i2=i1;i2<=r;i2++)
		{
			cout<<i1<<"-"<<i2<<endl;
			for(ll i=1;i<=n;i++)
			{
				for(ll j=1;j<=m;j++)
				{
					if(dp[i1][i2][i][j]<INF)cout<<dp[i1][i2][i][j];
					else cout<<"x";
				}
				cout<<endl;
			}
		}
	}*/
	ll ans=INF;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			ans=min(ans,dp[1][r][i][j]);
		}
	}
	if(ans==INF)cout<<"-1\n";
	else cout<<ans<<endl;
return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31212 KB Output is correct
2 Correct 22 ms 31212 KB Output is correct
3 Correct 22 ms 31212 KB Output is correct
4 Correct 22 ms 31468 KB Output is correct
5 Correct 22 ms 31468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31212 KB Output is correct
2 Correct 22 ms 31212 KB Output is correct
3 Correct 22 ms 31212 KB Output is correct
4 Correct 22 ms 31468 KB Output is correct
5 Correct 22 ms 31468 KB Output is correct
6 Correct 22 ms 31212 KB Output is correct
7 Correct 22 ms 31212 KB Output is correct
8 Correct 22 ms 31252 KB Output is correct
9 Correct 22 ms 31212 KB Output is correct
10 Correct 22 ms 31468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31212 KB Output is correct
2 Correct 22 ms 31212 KB Output is correct
3 Correct 22 ms 31212 KB Output is correct
4 Correct 22 ms 31468 KB Output is correct
5 Correct 22 ms 31468 KB Output is correct
6 Correct 22 ms 31212 KB Output is correct
7 Correct 22 ms 31212 KB Output is correct
8 Correct 22 ms 31252 KB Output is correct
9 Correct 22 ms 31212 KB Output is correct
10 Correct 22 ms 31468 KB Output is correct
11 Correct 882 ms 161008 KB Output is correct
12 Correct 69 ms 59420 KB Output is correct
13 Correct 528 ms 128620 KB Output is correct
14 Correct 1263 ms 160928 KB Output is correct
15 Correct 855 ms 160800 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31212 KB Output is correct
2 Correct 22 ms 31212 KB Output is correct
3 Correct 22 ms 31212 KB Output is correct
4 Correct 22 ms 31468 KB Output is correct
5 Correct 22 ms 31468 KB Output is correct
6 Correct 22 ms 31212 KB Output is correct
7 Correct 22 ms 31212 KB Output is correct
8 Correct 22 ms 31252 KB Output is correct
9 Correct 22 ms 31212 KB Output is correct
10 Correct 22 ms 31468 KB Output is correct
11 Correct 882 ms 161008 KB Output is correct
12 Correct 69 ms 59420 KB Output is correct
13 Correct 528 ms 128620 KB Output is correct
14 Correct 1263 ms 160928 KB Output is correct
15 Correct 855 ms 160800 KB Output is correct
16 Runtime error 361 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -