oj.uz

Submission #338793

# Submission time Handle Problem Language Result Execution time Memory
338793 2020-12-23T22:47:12 Z couplefire Robots (APIO13_robots) C++17
100 / 100
 585 ms 138468 KB 
#include<algorithm>
#include<vector>
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<queue>
 
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define REP(i,m) for(int i=0;i<(int)m;++i)
#define REPN(i,m,in) for(int i=in;i<(int)m;++i)
#define ALL(t) (t).begin(),(t).end()
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define prl cerr<<"LINE "<<__LINE__<<" is called"<<endl
 
using namespace std;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' '; cerr<<endl ; }
 
typedef pair<int,int> pi;
typedef long long int lint;
const int INF=510000000;
 
char buf[505][505];
int dp[50][505][505];
 
pi g[505][505][4];
 
bool vis[505][505][4];
 
int n,w,h;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
pi rec(int y,int x,int d){
    pi& res=g[y][x][d];
	if(res.fr!=-1) return res;
	if(vis[y][x][d]) return res=mp(-2,-2);
	vis[y][x][d]=1;
 
	if(buf[y][x]=='A') d=(d+1)%4;
	if(buf[y][x]=='C') d=(d+3)%4;
 
	int px=x+dx[d],py=y+dy[d];
	if(px<0 || py<0 || px>=w || py>=h || buf[py][px]=='x'){
		return res=mp(y,x);
	}
	return res=rec(py,px,d);
}
 
pi pos[10];
int hsh[10][10];
 
void prep(int sy,int sx,int id){
	queue<pi> q;
	dp[hsh[id][id+1]][sy][sx]=0;
	q.push(mp(sy,sx));
 
	while(!q.empty()){
		pi cur=q.front();q.pop();
 
		REP(d,4){
			pi to=g[cur.fr][cur.sc][d];
 
			if(to.fr==-2) continue;
 
			if(dp[hsh[id][id+1]][to.fr][to.sc]!=-1) continue;
 
			dp[hsh[id][id+1]][to.fr][to.sc]=dp[hsh[id][id+1]][cur.fr][cur.sc]+1;
 
			q.push(to);
		}
	}
 
	REP(i,h) REP(j,w) if(dp[hsh[id][id+1]][i][j]==-1) dp[hsh[id][id+1]][i][j]=INF;
}
 
vector<pi> posByCost[500*501*10];
vector<int> used;
 
int main(){
	int cntt=0;
	REP(i,9) REPN(j,10,i+1) hsh[i][j]=cntt++;
	scanf("%d%d%d",&n,&w,&h);
 
	REP(i,h) scanf("%s",buf[i]);
	REP(i,h) REP(j,w){
		if(buf[i][j]>='1' && buf[i][j]<='9'){
			pos[buf[i][j]-'1']=mp(i,j);
		}
	}
	memset(g,-1,sizeof(g));
	REP(i,h) REP(j,w) REP(d,4) rec(i,j,d);
 
	memset(dp,-1,sizeof(dp));
	REP(i,n){
		prep(pos[i].fr,pos[i].sc,i);
	}
 
 
	queue<pi> q;
 
	for(int len=2;len<=n;++len) REP(i,n-len+1){
		int j=i+len;
 
		pair<int,pi> mini;mini.fr=INF;
 
		REP(y,h) REP(x,w){
			dp[hsh[i][j]][y][x]=INF;
			REP(k,len-1){
				int div=i+k+1;
				dp[hsh[i][j]][y][x]=min(dp[hsh[i][j]][y][x],dp[hsh[i][div]][y][x]+dp[hsh[div][j]][y][x]);
			}
			if(dp[hsh[i][j]][y][x]!=INF){
				used.pb(dp[hsh[i][j]][y][x]);
				posByCost[dp[hsh[i][j]][y][x]].pb(mp(y,x));
				mini=min(mini,mp(dp[hsh[i][j]][y][x],mp(y,x)));
			}
		}
		if(mini.fr==INF) continue;
		REP(k,posByCost[mini.fr].size()) q.push(posByCost[mini.fr][k]);
		posByCost[mini.fr].clear();
 
 
		while(!q.empty()){
 
			pi p=q.front();q.pop();
			int c=dp[hsh[i][j]][p.fr][p.sc];
			if(!posByCost[c+1].empty()){
				REP(k,posByCost[c+1].size()){
					pi p2=posByCost[c+1][k];
					if(dp[hsh[i][j]][p2.fr][p2.sc]<c+1) continue;
					q.push(p2);
				}
				posByCost[c+1].clear();
			}
			REP(d,4){
				pi nxt=g[p.fr][p.sc][d];
				if(nxt.fr==-2 || dp[hsh[i][j]][nxt.fr][nxt.sc]<=c+1) continue;
				dp[hsh[i][j]][nxt.fr][nxt.sc]=c+1;
				q.push(nxt);
			}
 
		}
		REP(k,used.size()) posByCost[used[k]].clear();
		used.clear();
 
 
	}
 
	int res=INF;
 
	REP(i,h) REP(j,w) res=min(res,dp[hsh[0][n]][i][j]);
 
	if(res==INF) res=-1;
 
	printf("%d\n",res);
 
 
 
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d%d%d",&n,&w,&h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:86:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  REP(i,h) scanf("%s",buf[i]);
      |           ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117100 KB Output is correct
2 Correct 61 ms 117100 KB Output is correct
3 Correct 62 ms 117100 KB Output is correct
4 Correct 61 ms 117100 KB Output is correct
5 Correct 63 ms 117100 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117100 KB Output is correct
2 Correct 61 ms 117100 KB Output is correct
3 Correct 62 ms 117100 KB Output is correct
4 Correct 61 ms 117100 KB Output is correct
5 Correct 63 ms 117100 KB Output is correct
6 Correct 61 ms 117100 KB Output is correct
7 Correct 61 ms 117100 KB Output is correct
8 Correct 60 ms 117100 KB Output is correct
9 Correct 62 ms 117100 KB Output is correct
10 Correct 61 ms 117100 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117100 KB Output is correct
2 Correct 61 ms 117100 KB Output is correct
3 Correct 62 ms 117100 KB Output is correct
4 Correct 61 ms 117100 KB Output is correct
5 Correct 63 ms 117100 KB Output is correct
6 Correct 61 ms 117100 KB Output is correct
7 Correct 61 ms 117100 KB Output is correct
8 Correct 60 ms 117100 KB Output is correct
9 Correct 62 ms 117100 KB Output is correct
10 Correct 61 ms 117100 KB Output is correct
11 Correct 143 ms 121376 KB Output is correct
12 Correct 68 ms 117868 KB Output is correct
13 Correct 89 ms 118124 KB Output is correct
14 Correct 235 ms 123880 KB Output is correct
15 Correct 122 ms 119036 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117100 KB Output is correct
2 Correct 61 ms 117100 KB Output is correct
3 Correct 62 ms 117100 KB Output is correct
4 Correct 61 ms 117100 KB Output is correct
5 Correct 63 ms 117100 KB Output is correct
6 Correct 61 ms 117100 KB Output is correct
7 Correct 61 ms 117100 KB Output is correct
8 Correct 60 ms 117100 KB Output is correct
9 Correct 62 ms 117100 KB Output is correct
10 Correct 61 ms 117100 KB Output is correct
11 Correct 143 ms 121376 KB Output is correct
12 Correct 68 ms 117868 KB Output is correct
13 Correct 89 ms 118124 KB Output is correct
14 Correct 235 ms 123880 KB Output is correct
15 Correct 122 ms 119036 KB Output is correct
16 Correct 183 ms 118508 KB Output is correct
17 Correct 585 ms 138468 KB Output is correct
18 Correct 203 ms 121952 KB Output is correct
19 Correct 177 ms 118636 KB Output is correct
20 Correct 353 ms 131292 KB Output is correct