QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #704572 | #557. 街道 | TheZone | 100 ✓ | 3ms | 15232kb | C++11 | 6.5kb | 2024-11-02 20:15:12 | 2024-11-02 20:15:12 |
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;
}
/*#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);
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;
}*/
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 9160kb
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: 2ms
memory: 12420kb
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 -1...
output:
300015
result:
ok single line: '300015'
Test #3:
score: 10
Accepted
time: 0ms
memory: 15232kb
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 ...
output:
198
result:
ok single line: '198'
Test #4:
score: 10
Accepted
time: 2ms
memory: 4544kb
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 ...
output:
13697
result:
ok single line: '13697'
Test #5:
score: 10
Accepted
time: 2ms
memory: 4256kb
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 40...
output:
7344
result:
ok single line: '7344'
Test #6:
score: 10
Accepted
time: 3ms
memory: 8228kb
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 964...
output:
81482
result:
ok single line: '81482'
Test #7:
score: 10
Accepted
time: 0ms
memory: 4536kb
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...
output:
21394
result:
ok single line: '21394'
Test #8:
score: 10
Accepted
time: 2ms
memory: 4552kb
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 -466...
output:
10003995
result:
ok single line: '10003995'
Test #9:
score: 10
Accepted
time: 3ms
memory: 7876kb
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 5...
output:
3999530104
result:
ok single line: '3999530104'
Test #10:
score: 10
Accepted
time: 3ms
memory: 4336kb
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 999...
output:
3999216809
result:
ok single line: '3999216809'