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 |
|
|
|
|
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 |