Submission #1226108


Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000000000000ll
#define N 1000005
#define M 4000005
using namespace std;

const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int H,W,n,cnt,C,tot,fst[N],pnt[M],nxt[M];
int hsh[2010527],nxt_h[M],mn[M],pos[N];
ll d[N],len[M]; bool bo[N];
struct node{ int x,y,z,id; }p[N];
int getdct(char c){
	if (c=='N') return 0; else if (c=='S') return 1;
	else if (c=='W') return 2; else return 3;
}
int calc(int x,int y,int z){
	//if (x<=0 || x>H || y<=0 || y>W) return 0;
	int t=(x*100000ll+y)%2010527,i;
	for (i=hsh[t]; i; i=nxt_h[i]) if (p[i].x==x && p[i].y==y && p[i].z==z) return i;
		//cout<<x<<' '<<y<<' '<<z<<' '<<cnt+1<<endl;
	cnt++; p[cnt]=(node){x,y,z,cnt}; nxt_h[cnt]=hsh[t]; hsh[t]=cnt;
	return cnt;
}
void add(int x,int y,ll z){
	if (!x || !y) return;
	//	cout<<"				"<<x<<' '<<y<<' '<<z<<endl;
	pnt[++tot]=y; len[tot]=z; nxt[tot]=fst[x]; fst[x]=tot;
}
void build(int k,int l,int r){
	mn[k]=l; if (l==r){ pos[l]=k; return; }
	int mid=l+r>>1;
	build(k<<1,l,mid); build(k<<1|1,mid+1,r);
}
void mdy(int x){
	int i;
	for (i=pos[x]>>1; i; i>>=1)
		mn[i]=(d[mn[i<<1]]<d[mn[i<<1|1]])?mn[i<<1]:mn[i<<1|1];
}
bool cmpx(node u,node v){
	return u.x<v.x || u.x==v.x && u.y<v.y || u.x==v.x && u.y==v.y && u.z<v.z;
}
bool cmpy(node u,node v){
	return u.y<v.y || u.y==v.y && u.x<v.x || u.x==v.x && u.y==v.y && u.z<v.z;
}
int main(){
	scanf("%d%d%d%d",&H,&W,&n,&C);
	int x1,x2,y1,y2,i,j,k,l,x,y,cst; char c;
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	calc(x1,y1,0); calc(x2,y2,0);
	for (i=1; i<=2; i++) add(calc(x2,y2,i),calc(x2,y2,0),0);
	for (i=1; i<=n; i++){
		scanf("%d%d %c%d%d",&x,&y,&c,&l,&cst);
	//	cout<<"("<<c<<")"<<endl;
		k=getdct(c);
	//	cout<<k<<endl;
	//	cout<<x<<' '<<y<<' '<<c<<' '<<l<<' '<<cst<<endl;
		for (j=1; j<=2; j++)
			add(calc(x,y,j),calc(x,y,0),0);
		for (j=0; j<4; j++)
			add(calc(x,y,0),calc(x+dx[j]*l,y+dy[j]*l,(j>1)?1:2),(j==k)?0:cst);
	}
	//cout<<cnt<<endl;
	sort(p+1,p+cnt+1,cmpx);
	for (i=1; i<=cnt; i=j)
		for (j=i,k=0; p[i].x==p[j].x; j++){
		//	cout<<p[j].x<<' '<<p[j].y<<' '<<p[j].z<<endl;
			if (p[j].z==1){
				add(p[j].id,p[k].id,(ll)(p[j].y-p[k].y)*C);
				add(p[k].id,p[j].id,(ll)(p[j].y-p[k].y)*C);
				k=j;
			}
		}
	sort(p+1,p+cnt+1,cmpy);
	for (i=1; i<=cnt; i=j)
		for (j=i,k=0; p[i].y==p[j].y; j++)
			if (p[j].z==2){
				add(p[j].id,p[k].id,(ll)(p[j].x-p[k].x)*C);
				add(p[k].id,p[j].id,(ll)(p[j].x-p[k].x)*C);
				k=j;
			}
	for (i=2; i<=cnt; i++) d[i]=inf;
	memset(bo,1,sizeof(bo));
	build(1,1,cnt);
	for (i=1; i<=cnt; i++){
		x=mn[1]; if (x==2) break;
		bo[x]=0;
		for (j=fst[x]; j; j=nxt[j]){
			y=pnt[j];
			if (bo[y] && d[x]+len[j]<d[y]){
		//	cout<<x<<"->"<<y<<endl;
				d[y]=d[x]+len[j]; mdy(y);
			}
		}
		d[x]=inf; mdy(x);
	}
	printf("%lld\n",(d[2]<inf)?d[2]:-1);
	return 0;
}

Submission Info

Submission Time
Task F - Find the Route!
User lych_cys
Language C++14 (GCC 5.4.1)
Score 1150
Code Size 2873 Byte
Status AC
Exec Time 298 ms
Memory 73984 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:47:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&H,&W,&n,&C);
                               ^
./Main.cpp:49:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                                   ^
./Main.cpp:53:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d %c%d%d",&x,&y,&c,&l,&cst);
                                        ^

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 190 / 190 170 / 170 360 / 360 430 / 430
Status
AC × 3
AC × 3
AC × 10
AC × 15
Set Name Test Cases
Subtask1 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt
Subtask2 sub2_in1.txt, sub2_in2.txt, sub2_in3.txt
Subtask3 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt
Subtask4 sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub4_in5.txt
Case Name Status Exec Time Memory
sub1_in1.txt AC 8 ms 35072 KB
sub1_in2.txt AC 8 ms 35072 KB
sub1_in3.txt AC 8 ms 35072 KB
sub2_in1.txt AC 7 ms 30976 KB
sub2_in2.txt AC 9 ms 35072 KB
sub2_in3.txt AC 12 ms 35200 KB
sub3_in1.txt AC 12 ms 35200 KB
sub3_in2.txt AC 196 ms 63744 KB
sub3_in3.txt AC 225 ms 65792 KB
sub3_in4.txt AC 298 ms 71936 KB
sub4_in1.txt AC 136 ms 59648 KB
sub4_in2.txt AC 238 ms 69888 KB
sub4_in3.txt AC 212 ms 67840 KB
sub4_in4.txt AC 239 ms 73984 KB
sub4_in5.txt AC 199 ms 55552 KB