QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167276#7184. Transport Plusesucup-team266#WA 241ms4312kbC++142.5kb2023-09-07 13:22:022023-09-07 13:22:02

Judging History

你现在查看的是最新测评结果

  • [2023-09-07 13:22:02]
  • 评测
  • 测评结果:WA
  • 用时:241ms
  • 内存:4312kb
  • [2023-09-07 13:22:02]
  • 提交

answer

/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,t;
int sx,sy,tx,ty;
int X[105],Y[105];
int okx[105],oky[105];
int dist[105][105],vis[105][105];
array<int,3> prv[105][105];
void solve()
{
	cin>>n>>t;
	cin>>sx>>sy>>tx>>ty;
	for(int i=1;i<=n;i++) cin>>X[i]>>Y[i];
	memset(dist,0x3f,sizeof(dist));
	memset(prv,-1,sizeof(prv));
	dist[sx][sy]=0;
	int tot=0;
	while(1)
	{
		int x=-1,y=-1;
		for(int i=0;i<=100;i++) for(int j=0;j<=100;j++) if(!vis[i][j])
		{
			if(x==-1) x=i,y=j;
			else if(dist[i][j]<dist[x][y]) x=i,y=j;
		}
		if(x==-1) break;
		tot++;
//		cout<<x<<" "<<y<<" "<<tot<<"\n";
		vis[x][y]=1;
		memset(okx,0,sizeof(okx));
		memset(oky,0,sizeof(oky));
		for(int i=1;i<=n;i++) if(X[i]==x||Y[i]==y) okx[X[i]]=oky[Y[i]]=1;
		for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
		{
			if(i==x&&dist[x][y]+abs(j-y)<dist[i][j]) dist[i][j]= dist[x][y]+abs(j-y),prv[i][j]={0,x,y};
			if(j==y&&dist[x][y]+abs(i-x)<dist[i][j]) dist[i][j]=dist[x][y]+abs(i-x),prv[i][j]={0,x,y};
			if((okx[i]||oky[j])&&dist[x][y]+t<dist[i][j]) dist[i][j]=dist[x][y]+t,prv[i][j]={1,x,y}; 
		 } 
	}
	
	double ans=1e9;
	int x=-1,y=-1;
	for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
	{
		int d=(i-tx)*(i-tx)+(j-ty)*(j-ty);
		double nw=(double)(dist[i][j])+(double)(sqrt((double)(d)));
		if(nw<ans) ans=nw,x=i,y=j; 
	}
	vector <array<int,3> > ansv; 
	cout<<fixed<<setprecision(12)<<ans<<"\n";
	if(x!=tx||y!=ty) ansv.pb({0,tx,ty});
	while(1)
	{
		int op=prv[x][y][0],x2=prv[x][y][1],y2=prv[x][y][2];
		if(op==-1) break;
		ansv.pb({op,x,y});
		x=x2,y=y2;
	}
	cout<<ansv.size()<<"\n";
	for(int i=(int)(ansv.size())-1;i>=0;i--) cout<<ansv[i][0]<<" "<<ansv[i][1]<<" "<<ansv[i][2]<<"\n";
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 241ms
memory: 4312kb

input:

1 2
1 1
5 3
6 2

output:

4.000000000000
3
0 1 2
1 5 2
0 5 3

result:

ok correct

Test #2:

score: -100
Wrong Answer
time: 240ms
memory: 4176kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2.000000000000
2
1 0 3
1 6 1

result:

wrong answer step 2: target (6.000000, 1.000000) not on plus (1.000000, 3.000000)