QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#8717 | #557. 街道 | LCGUO | 100 ✓ | 8ms | 16940kb | C++20 | 3.8kb | 2021-04-03 20:50:14 | 2021-12-19 10:52:52 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=1000010,N=10010;
typedef long long ll;
typedef double db;
int n,zn,hn;
struct line{int x,y,l;}z[N],h[N];
int ct;
vector<pair<int,int> >hj[N],zj[N];
int head[maxn],to[maxn],nxt[maxn],cot[maxn],cnt;
inline void addedge(int u,int v,int w){++cnt,to[cnt]=v,nxt[cnt]=head[u],head[u]=cnt,cot[cnt]=w;}
queue<int>q;
ll dis[100010];
inline void spfa(){
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
q.push(0);
while(!q.empty()){
int u=q.front();q.pop();
for(register int e=head[u];e;e=nxt[e]){
int v=to[e];
if(dis[u]+cot[e]<dis[v]){
dis[v]=dis[u]+cot[e];
q.push(v);
}
}
}
}
inline void solve(){
for(register int i=1;i<=n;++i){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
}
ll sx,sy,tx,ty;scanf("%lld%lld%lld%lld",&sx,&sy,&tx,&ty);
printf("%lld\n",abs(sx-tx)+abs(sy-ty));
}
int main(){
scanf("%d",&n);
if(n>200){solve();return 0;}
for(register int i=1;i<=n;++i){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2)swap(x1,x2),swap(y1,y2);
if(y1>y2)swap(x1,x2),swap(y1,y2);
if(x1<x2)++hn,h[hn].x=x1,h[hn].y=y1,h[hn].l=x2-x1;
if(y1<y2)++zn,z[zn].x=x1,z[zn].y=y1,z[zn].l=y2-y1;
}
ct=2*n;
for(register int i=1;i<=hn;++i)
for(register int j=1;j<=zn;++j)
if(z[j].x>=h[i].x&&z[j].x<=h[i].x+h[i].l&&z[j].y<=h[i].y&&z[j].y+z[j].l>=h[i].y){
++ct;
hj[i].push_back(make_pair(z[j].x,ct));
zj[j].push_back(make_pair(h[i].y,ct));
}
int sx,sy,tx,ty;
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
for(register int i=1;i<=hn;++i){
if(sx>=h[i].x&&sx<=h[i].x+h[i].l&&sy==h[i].y)hj[i].push_back(make_pair(sx,0));
if(tx>=h[i].x&&tx<=h[i].x+h[i].l&&ty==h[i].y)hj[i].push_back(make_pair(tx,ct+1));
}
for(register int i=1;i<=zn;++i){
if(sy>=z[i].y&&sy<=z[i].y+z[i].l&&sx==z[i].x)zj[i].push_back(make_pair(sy,0));
if(ty>=z[i].y&&ty<=z[i].y+z[i].l&&tx==z[i].x)zj[i].push_back(make_pair(ty,ct+1));
}
for(register int i=1;i<=hn;++i){
sort(hj[i].begin(),hj[i].end());
if(hj[i].size ()==0)addedge(2*i-1,2*i,h[i].l),addedge(2*i,2*i-1,h[i].l);
else{
addedge(2*i-1,hj[i][0].second,hj[i][0].first-h[i].x);
addedge(hj[i][0].second,2*i-1,hj[i][0].first-h[i].x);
for(register unsigned int p=0; p<hj[i].size()-1;++p)
addedge(hj[i][p].second,hj[i][p+1].second,hj[i][p+1].first-hj[i][p].first),
addedge(hj[i][p+1].second,hj[i][p].second,hj[i][p+1].first-hj[i][p].first);
addedge(hj[i][hj[i].size()-1].second,2*i,h[i].x+h[i].l-hj[i][hj[i].size()-1].first);
addedge(2*i,hj[i][hj[i].size()-1].second,h[i].x+h[i].l-hj[i][hj[i].size()-1].first);
}
}
for(register int i=1;i<=zn;++i){
sort(zj[i].begin(),zj[i].end());
if(zj[i].size()==0)addedge(2*hn+2*i-1,2*hn+2*i,z[i].l),addedge(2*hn+2*i,2*hn+2*i-1,z[i].l);
else{
addedge(2*hn+2*i-1,zj[i][0].second,zj[i][0].first-z[i].y);
addedge(zj[i][0].second,2*hn+2*i-1,zj[i][0].first-z[i].y);
for(register unsigned int p=0;p<zj[i].size()-1;++p)
addedge(zj[i][p].second,zj[i][p+1].second,zj[i][p+1].first-zj[i][p].first),
addedge(zj[i][p+1].second,zj[i][p].second,zj[i][p+1].first-zj[i][p].first);
addedge(zj[i][zj[i].size()-1].second,2*hn+2*i,z[i].y+z[i].l-zj[i][zj[i].size()-1].first);
addedge(2*hn+2*i,zj[i][zj[i].size()-1].second,z[i].y+z[i].l-zj[i][zj[i].size()-1].first);
}
}
for(register int i=1;i<=hn;++i)
for(register int j=1;j<=hn;++j)if(i!=j&&h[i].y==h[j].y)
if(h[i].x==h[j].x+h[j].l)addedge(2*i-1,2*j,0),addedge(2*j,2*i-1,0);
for(register int i=1;i<=zn;++i)
for(register int j=1;j<=zn;++j)if(i!=j&&z[i].x==z[j].x)
if(z[i].y==z[j].y+z[j].l)addedge(2*hn+2*i-1,2*hn+2*j,0),addedge(2*hn+2*j,2*hn+2*i-1,0);
spfa();
printf("%lld\n",dis[ct+1]);
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 3ms
memory: 14388kb
input:
10 0 0 0 3 1 0 1 3 2 0 2 3 3 0 3 3 0 0 3 0 -1 1 4 1 -1 1 -1 10000 4 1 4 10000 -1000 10000 1000 10000 0 5000 0 10000 2 3 0 5000
output:
15005
result:
ok single line: '15005'
Test #2:
score: 10
Accepted
time: 4ms
memory: 14444kb
input:
19 -100000 0 100000 0 -100000 0 -100000 100000 100000 0 100000 100000 -100000 100000 100000 100000 10000 0 10000 10 -10000 0 -10000 10 -10000 10 10000 10 -10000 99999 -10000 100000 -10001 99999 -10000 99999 -10001 99998 -10001 99999 -10002 99998 -10001 99998 -10002 99997 -10002 99998 -10003 99997 -10002 99997 10000 99999 10000 100000 10000 99999 10001 99999 10001 99998 10001 99999 10001 99998 10002 99998 10002 99997 10002 99998 10002 99997 10003 99997 9999 10 -10003 99997
output:
300015
result:
ok single line: '300015'
Test #3:
score: 10
Accepted
time: 1ms
memory: 16940kb
input:
200 0 0 99 0 0 1 99 1 0 2 99 2 0 3 99 3 0 4 99 4 0 5 99 5 0 6 99 6 0 7 99 7 0 8 99 8 0 9 99 9 0 10 99 10 0 11 99 11 0 12 99 12 0 13 99 13 0 14 99 14 0 15 99 15 0 16 99 16 0 17 99 17 0 18 99 18 0 19 99 19 0 20 99 20 0 21 99 21 0 22 99 22 0 23 99 23 0 24 99 24 0 25 99 25 0 26 99 26 0 27 99 27 0 28 99 28 0 29 99 29 0 30 99 30 0 31 99 31 0 32 99 32 0 33 99 33 0 34 99 34 0 35 99 35 0 36 99 36 0 37 99 37 0 38 99 38 0 39 99 39 0 40 99 40 0 41 99 41 0 42 99 42 0 43 99 43 0 44 99 44 0 45 99 45 0 46 99 46...
output:
198
result:
ok single line: '198'
Test #4:
score: 10
Accepted
time: 6ms
memory: 8160kb
input:
10000 -4185 4931 -4185 9055 -957 -3447 9708 -3447 -3799 -8611 4306 -8611 -3454 -9662 7938 -9662 -2030 -6055 -1067 -6055 1746 3897 3533 3897 5764 -6035 5764 9951 7178 -3198 7178 8165 -9577 6633 -7052 6633 2133 -5934 2133 9608 -7241 -2537 4939 -2537 -6343 -2783 5590 -2783 -8383 -2403 -8383 -588 -8003 2260 -5342 2260 -5294 8437 -4985 8437 1494 -2085 3576 -2085 2222 7632 7471 7632 -9327 -4538 5138 -4538 -4734 -3031 3150 -3031 1427 -8665 1427 2524 1004 -6743 1004 -3908 7852 -9951 7852 9480 6205 -7265...
output:
13697
result:
ok single line: '13697'
Test #5:
score: 10
Accepted
time: 6ms
memory: 4088kb
input:
10000 -5616 -9030 -684 -9030 -9818 8296 7371 8296 2007 1038 2007 7814 -7752 -6096 5591 -6096 -9250 -7645 -9250 2801 -9211 7265 8090 7265 6227 -7435 6227 -3303 9915 5267 9915 7897 6717 -9060 6717 -6918 -4118 2321 -1661 2321 26 -6333 26 4397 1081 -3684 6538 -3684 -6684 -893 -590 -893 3363 4069 4463 4069 -5484 -4260 129 -4260 -6323 354 4401 354 71 2995 1055 2995 327 -6588 327 -2924 -4440 3002 5406 3002 -6270 -7829 -6270 2418 2215 1753 2215 6149 -1113 2200 -1113 5032 -9679 -7291 -9679 -6345 6178 -44...
output:
7344
result:
ok single line: '7344'
Test #6:
score: 10
Accepted
time: 6ms
memory: 4120kb
input:
10000 4192 91321 71384 91321 -58131 -78890 6829 -78890 -11187 65474 62707 65474 -53772 -49957 9067 -49957 -49366 -74857 12088 -74857 -74394 66156 -12638 66156 50664 -11123 61539 -11123 -60147 48454 85870 48454 3682 58827 95706 58827 -66729 59832 -31692 59832 -5295 -37887 -5295 34301 87081 -56045 96407 -56045 -70754 27862 -70754 38870 47658 6987 64941 6987 -90977 -98339 70266 -98339 -49140 -75419 63585 -75419 -33903 14933 31962 14933 -24542 -1980 -24542 68041 -34772 -23159 78466 -23159 -85419 -80...
output:
81482
result:
ok single line: '81482'
Test #7:
score: 10
Accepted
time: 7ms
memory: 7936kb
input:
10000 -7384 2627 -6777 2627 5618 -5900 6848 -5900 -9287 -8259 -9287 3419 -9285 -4001 -9285 5869 4663 9897 6926 9897 6763 -4673 8047 -4673 -7036 1898 -4433 1898 -7929 -9131 -7929 -8704 6219 -7314 6219 3072 466 7137 2627 7137 3223 -4946 7223 -4946 -7706 -1969 -3585 -1969 -9924 9878 -9425 9878 262 -260 1756 -260 6211 4454 6211 4607 -586 -5014 -586 699 1232 -583 1232 6098 -1521 -6967 -1521 6125 -9919 -2817 8049 -2817 2737 -3212 6694 -3212 -9006 6149 4265 6149 -7522 -2883 -7122 -2883 -5478 -5004 -547...
output:
21394
result:
ok single line: '21394'
Test #8:
score: 10
Accepted
time: 3ms
memory: 4192kb
input:
9998 -33637007 1 -1 1 -56452802 3 -1 3 -91875837 5 -1 5 -15180755 7 -1 7 -7507358 9 -1 9 -1697168 11 -1 11 -92331674 13 -1 13 -7021474 15 -1 15 -31799292 17 -1 17 -24320416 19 -1 19 -39357763 21 -1 21 -95501201 23 -1 23 -43076212 25 -1 25 -51660291 27 -1 27 -39534586 29 -1 29 -20389863 31 -1 31 -46680459 33 -1 33 -33977051 35 -1 35 -40892525 37 -1 37 -12013473 39 -1 39 -27503640 41 -1 41 -71657145 43 -1 43 -48799629 45 -1 45 -48190765 47 -1 47 -14191598 49 -1 49 -83044152 51 -1 51 -24504267 53 -...
output:
10003995
result:
ok single line: '10003995'
Test #9:
score: 10
Accepted
time: 0ms
memory: 7736kb
input:
9999 896754241 507943864 999643867 507943864 -999967762 658538790 293617239 658538790 920932906 -178746677 999643867 -178746677 -999967762 -439833588 -457555758 -439833588 -999967762 -269462675 999643867 -269462675 -999967762 -569155444 999643867 -569155444 -999967762 283408427 999643867 283408427 555247176 -594452338 555247176 999989600 -999967762 -107516414 999643867 -107516414 739869546 -999928875 739869546 999989600 -790469384 -999928875 -790469384 999989600 -999967762 189375760 999643867 18...
output:
3999530104
result:
ok single line: '3999530104'
Test #10:
score: 10
Accepted
time: 8ms
memory: 6112kb
input:
10000 -999899212 -999778368 -999899212 999451782 -999779028 -999778368 -999779028 999451782 -999534628 -999778368 -999534628 999451782 -999325484 -999778368 -999325484 999451782 -999294214 -999778368 -999294214 999451782 -998826678 -999778368 -998826678 999451782 -998525906 -999778368 -998525906 999451782 -998398800 -999778368 -998398800 999451782 -998294222 -999778368 -998294222 999451782 -998236046 -999778368 -998236046 999451782 -998030728 -999778368 -998030728 999451782 -997752930 -999778368...
output:
3999216809
result:
ok single line: '3999216809'