QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#5869#557. 街道Qingyu100 ✓6ms14676kbC++983.8kb2021-01-26 00:37:582021-12-19 07:05:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 07:05:08]
  • 评测
  • 测评结果:100
  • 用时:6ms
  • 内存:14676kb
  • [2021-01-26 00:37:58]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 4ms
memory: 11008kb

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: 11084kb

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: 2ms
memory: 14676kb

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: 4148kb

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: 5ms
memory: 4080kb

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: 1ms
memory: 7780kb

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: 6ms
memory: 7924kb

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: 0ms
memory: 4152kb

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: 4ms
memory: 7704kb

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: 2ms
memory: 4080kb

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'