QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#734815#7671. Metal Processing PlantffffycAC ✓574ms6708kbC++143.4kb2024-11-11 15:17:132024-11-11 15:17:14

Judging History

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

  • [2024-11-11 15:17:14]
  • 评测
  • 测评结果:AC
  • 用时:574ms
  • 内存:6708kb
  • [2024-11-11 15:17:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
	inline char getc(){
		char ch=gh();
		while(ch<'A'||ch>'Z') ch=gh();
		return ch;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=400+10,INF=1e9+10;
int n,d[N][N];
struct node{
	int u,v,w;
	inline friend bool operator<(const node &a,const node &b){
		return a.w>b.w;
	}
};
vector<node>vec;
vector<int>a[N],b[N];
int vis[N][2];
inline int bfs(int s,int t){
	for(int i=1;i<=n;i++)
		vis[i][0]=vis[i][1]=0;
	vis[s][0]=1;
	queue<pii>q;
	q.push(mpr(s,0));
	while(!q.empty()){
		int x=q.front().fir,d=q.front().sec;
		q.pop();
		for(auto t:a[x])
			if(!vis[t][!d])
				vis[t][!d]=1,q.push(mpr(t,!d));
	}
	if(vis[t][0]) return -1;
	if(vis[t][1]) return 1;
	return 0;
}
int dfn[N],low[N],stk[N],top,bel[N],tim,inc[N],bc;
inline void Tarjan(int x){
	dfn[x]=low[x]=++tim,stk[++top]=x,inc[x]=1;
	for(auto t:b[x]){
		if(!dfn[t]) Tarjan(t),low[x]=min(low[x],low[t]);
		else if(inc[t]) low[x]=min(low[x],dfn[t]);
	}
	if(dfn[x]==low[x]){
		bc++;
		while(1){
			int p=stk[top--];
			inc[p]=0,bel[p]=bc;
			if(p==x) break;
		}
	}
}
inline void clear(){
	for(int i=1;i<=n*2;i++)
		b[i].clear();
	for(int i=1;i<=n*2;i++)
		dfn[i]=bel[i]=inc[i]=0;
	tim=bc=0;
}
inline bool check(int x){
//	printf("---check(%d)---\n",x);
	for(int i=1;i<=n;i++)
		for(auto j:a[i])
			b[i].push_back(j+n);//,printf("%d %d\n",i,j+n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(d[i][j]>x)
				b[i+n].push_back(j);//,printf("%d %d\n",i+n,j);
	for(int i=1;i<=n*2;i++)
		if(!dfn[i])
			Tarjan(i);
	bool fl=1;
	for(int i=1;i<=n;i++)
		if(bel[i]==bel[i+n])
			fl=0;
//	for(int i=1;i<=n;i++)
//		printf("(%d,%d) ",bel[i],bel[i+n]);puts("");
//	for(int i=1;i<=n;i++)
//		printf(bel[i]>bel[i+n]?"B":"A");
//	puts("");
	clear();
	return fl;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			vec.push_back({i,j,d[i][j]=d[j][i]=read()});
	if(n<=2) return puts("0"),0;
	sort(vec.begin(),vec.end());
//	for(int i=1;i<=n;i++,puts(""))
//		for(int j=1;j<=n;j++)
//			printf("%3d ",d[i][j]);
	int ans=INF*2,fl=0;
	for(auto e:vec){
		int u=e.u,v=e.v;
		int tp=bfs(u,v);
//		printf("(%d,%d) %d\n",u,v,e.w);
		if(tp!=1){
			int L=0,R=vec.size()-1,res=-1;
			if(check(0)) res=0;
			else{
				while(L<=R){
					int mid=L+R>>1;
					if(check(vec[mid].w)) L=mid+1,res=vec[mid].w;
					else R=mid-1;
				}
			}
//			printf("%d %d\n",e.w,res);
			if(res!=-1) ans=min(ans,e.w+res);
		}
		if(tp==-1){ fl=1;break; }
		a[u].push_back(v);
		a[v].push_back(u);
	}
	write(ans);
	flush();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

5
4 5 0 2
1 3 7
2 0
4

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

7
1 10 5 5 5 5
5 10 5 5 5
100 100 5 5
10 5 5
98 99
3

output:

15

result:

ok single line: '15'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

1

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5628kb

input:

2
1

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2
1000000000

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

3
1000000000 1000000000
1000000000

output:

1000000000

result:

ok single line: '1000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 5692kb

input:

4
1000000000 1000000000 1000000000
1000000000 1000000000
1000000000

output:

1000000000

result:

ok single line: '1000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 5932kb

input:

3
78 97
24

output:

24

result:

ok single line: '24'

Test #9:

score: 0
Accepted
time: 423ms
memory: 4560kb

input:

200
202018752 202018795 202018793 100018905 202018758 202018741 202018727 202018766 202018728 100018879 202018781 100018860 202018785 100018841 100018910 100018836 100018883 100018847 202018734 202018775 100018830 100018901 202018773 202018754 202018737 100018843 202018788 202018778 202018777 202018...

output:

201024848

result:

ok single line: '201024848'

Test #10:

score: 0
Accepted
time: 417ms
memory: 6468kb

input:

200
202005938 100019219 100011585 100005992 202005976 202005911 100016762 100005984 100009020 202005957 202005897 202005983 202005890 100017500 100018445 100012670 202005892 100011737 202005963 202005972 100009700 100007735 100008624 100005986 100014474 100015862 100016219 100013970 202005950 100009...

output:

201024848

result:

ok single line: '201024848'

Test #11:

score: 0
Accepted
time: 418ms
memory: 6544kb

input:

200
100007374 202007324 202007273 100007871 202007284 202007349 202007346 202007350 100008506 202007326 202007328 100015874 100007372 100012524 100009032 202007285 100014317 100019231 100007996 100017887 100007379 202007268 100014999 100007365 100019036 202007271 202007309 202007288 100010706 202007...

output:

201024848

result:

ok single line: '201024848'

Test #12:

score: 0
Accepted
time: 417ms
memory: 4588kb

input:

200
202006587 100000504 100003353 202008547 100000526 202007172 202006935 100002517 100001410 202019338 100003773 100004592 100000735 100004037 202006027 202013398 202009902 202011058 202016868 100019535 202004982 202016142 100000502 202005597 202010043 202007413 202017798 202008417 202013073 100000...

output:

201024848

result:

ok single line: '201024848'

Test #13:

score: 0
Accepted
time: 422ms
memory: 4588kb

input:

200
202013592 100001907 202015993 100001947 202013923 202006848 202006503 100001892 202012308 100003548 100001917 202015815 100001893 100002015 202006057 202008063 100004622 202008577 100001918 100004433 100001902 100003890 202008840 100001897 202014090 100003803 100002078 100001930 202011997 202006...

output:

201024848

result:

ok single line: '201024848'

Test #14:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

6
1 2 4 5 6
3 7 8 9
10 11 12
1 2
3

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 457ms
memory: 4616kb

input:

200
435010275 394827075 822898985 583981988 396544171 388068327 705313071 387175158 376921468 924667109 385310238 388224555 372946359 675345877 702550462 487933667 882651877 370449115 384336752 378249505 780536986 506944725 920250961 689413504 389904013 386551860 481990426 679124822 391654021 394915...

output:

794876947

result:

ok single line: '794876947'

Test #16:

score: 0
Accepted
time: 574ms
memory: 4616kb

input:

200
91278452 415955592 137823215 314136215 85980089 112516050 99745487 404638548 296860352 72129392 102598663 95399022 162656397 101864519 118447999 96361202 75641337 122629487 327747335 129194224 116416669 309089970 338924615 160441557 111782426 333964646 186922874 118487863 326700618 230247496 175...

output:

246963817

result:

ok single line: '246963817'

Test #17:

score: 0
Accepted
time: 449ms
memory: 4520kb

input:

188
576794591 501148618 115086375 55250485 330862932 83023286 91365558 76262774 692432489 109599127 144624877 66264788 124023033 471300089 85045940 474857834 246237296 124592901 76208271 102850695 118276787 322641888 652258162 300701156 68595793 62803137 82882132 71792792 152434816 154919594 6307860...

output:

335173534

result:

ok single line: '335173534'

Test #18:

score: 0
Accepted
time: 283ms
memory: 4640kb

input:

189
102035989 96812803 258230955 271318394 203542836 104491726 100409868 123562651 289507007 117029262 109244526 100829396 270772917 159626392 828051016 151766620 263718763 252687973 143785192 220869210 180916527 174151816 96609354 284132615 191925255 264479964 120447766 107253792 669898981 10554141...

output:

580280382

result:

ok single line: '580280382'

Test #19:

score: 0
Accepted
time: 349ms
memory: 6328kb

input:

182
27878423 69811834 183815849 103797710 159171126 55276211 335707704 17592245 318616827 37595953 56157720 192535865 63822481 280549570 34027202 221569174 70447605 15919506 17263440 180118271 356820171 144194546 185393418 111014491 17903229 169853016 284064775 59192490 162261182 43257363 352135181 ...

output:

161870491

result:

ok single line: '161870491'

Test #20:

score: 0
Accepted
time: 213ms
memory: 4552kb

input:

182
300028836 303801181 275207620 205798427 223394990 203626485 216226328 205799565 303585928 219768488 216081701 247810308 277910184 200609363 611654913 234768445 250018119 190012959 552079766 244568440 321485025 258702937 221464941 281517602 276142808 204039196 204538209 306717326 216305622 195930...

output:

646154613

result:

ok single line: '646154613'

Test #21:

score: 0
Accepted
time: 395ms
memory: 6460kb

input:

189
322674255 353835269 189462856 49511638 411811754 32977498 464532918 249810819 473963712 486485939 54454078 34070551 45617736 52917376 49933281 142925270 144474693 339907596 178167612 324358168 408261119 46433627 29611986 169892943 199246722 25606037 70708831 46835362 26755447 367436904 31616619 ...

output:

118540676

result:

ok single line: '118540676'

Test #22:

score: 0
Accepted
time: 239ms
memory: 4656kb

input:

195
38843003 72009405 339697084 49125386 43890223 51136575 37884777 245281760 62773880 46603021 40623046 65136384 139481128 76470559 79851995 58321799 72462595 52899430 77349004 54162088 56062567 75878866 42137500 60980793 41900291 47612785 65949918 47768452 38943538 69505977 63569018 40291256 41317...

output:

164791372

result:

ok single line: '164791372'

Test #23:

score: 0
Accepted
time: 244ms
memory: 6708kb

input:

192
392164708 120868504 106102020 115253365 114150828 200259128 119395513 123030269 116170330 112794526 115221409 110710165 104352073 118243311 112579691 115250993 123492780 109538841 115934157 111868677 487647022 112960432 105874888 626788430 111443605 115755981 119543777 360062444 116323280 999363...

output:

248916412

result:

ok single line: '248916412'

Test #24:

score: 0
Accepted
time: 414ms
memory: 6540kb

input:

181
150132609 962550480 136404879 230383743 154539650 205033439 158270735 660495392 246197255 101728783 532089770 208000864 209987893 89595991 393183800 735266219 256195266 710469203 112349941 135323305 227934383 254629117 144982778 146155439 248056344 238304296 509276386 504751959 943742930 9295410...

output:

556506453

result:

ok single line: '556506453'

Test #25:

score: 0
Accepted
time: 231ms
memory: 6312kb

input:

183
316608062 369742324 371723569 154176404 861959484 178580933 338355707 215872342 320998485 359780127 404702270 156018577 366134553 117742267 401309219 308951606 345810540 141206702 131292637 143569145 116488265 266464705 314297814 276113637 214369604 162120417 192390988 345847575 285114230 394715...

output:

787543854

result:

ok single line: '787543854'

Test #26:

score: 0
Accepted
time: 488ms
memory: 6564kb

input:

197
260624679 268811010 158911919 161546469 180737636 45066827 260419919 182835067 30295467 290779234 129589092 197456928 74623538 48366482 173958805 267082743 123475951 265975322 416755392 95668580 250382727 113079598 72897084 63541037 108993957 45470413 149746556 286893151 266360511 61530374 67084...

output:

512725604

result:

ok single line: '512725604'

Test #27:

score: 0
Accepted
time: 110ms
memory: 4364kb

input:

200
914950134 556479224 76895799 836393714 890269358 859900773 792775593 479100273 502212098 135083824 718050042 853038513 825758063 463185023 414010327 345356515 215212868 217373201 517231660 686598843 572929731 542786469 222700969 595185096 468159187 835635128 472006378 258475691 351617658 5312095...

output:

999959104

result:

ok single line: '999959104'

Test #28:

score: 0
Accepted
time: 152ms
memory: 4296kb

input:

200
656 355 572 601 272 351 271 216 571 158 358 410 918 251 324 42 661 587 987 696 928 441 589 161 810 298 617 584 740 272 18 558 0 990 553 211 931 692 249 848 853 734 788 770 499 78 156 677 147 460 249 547 180 706 136 236 423 182 772 963 36 606 656 696 922 723 671 281 171 79 84 999 247 380 937 694 ...

output:

1000

result:

ok single line: '1000'

Test #29:

score: 0
Accepted
time: 3ms
memory: 4100kb

input:

200
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

ok single line: '0'

Test #30:

score: 0
Accepted
time: 28ms
memory: 6136kb

input:

200
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000...

output:

1000000000

result:

ok single line: '1000000000'

Test #31:

score: 0
Accepted
time: 471ms
memory: 4488kb

input:

200
221 151 212 65 230 120 290 272 341 63 344 89 111 60 146 216 227 191 50 80 120 14 276 71 218 136 24 1 40 49 103 296 143 166 142 58 157 33 42 25 216 293 122 154 102 171 109 76 292 154 137 31 374 164 177 283 28 320 303 119 184 348 319 206 192 58 291 247 290 349 93 45 284 153 14 96 254 68 80 163 191...

output:

189

result:

ok single line: '189'

Test #32:

score: 0
Accepted
time: 304ms
memory: 6444kb

input:

180
42 17 427 50 100 358 10 110 33 307 228 56 63 186 468 430 452 301 465 32 77 407 115 420 46 407 84 462 7 179 419 350 7 33 53 112 47 107 54 102 269 161 45 151 10 62 407 425 33 216 386 194 64 72 95 18 25 455 229 129 23 390 32 426 35 12 303 295 100 82 261 359 86 344 228 21 110 9 97 32 154 251 174 204...

output:

234

result:

ok single line: '234'

Test #33:

score: 0
Accepted
time: 442ms
memory: 4636kb

input:

198
90593707 246229613 253945130 368135009 209134562 301930486 541570368 8457737 94708897 482739227 141396699 92755363 308379601 39891707 69677960 206335102 231807769 83312286 518651540 37092920 97995198 552890645 126589379 134651647 94091541 376525685 473978397 54731656 56552444 505614754 289547009...

output:

277597482

result:

ok single line: '277597482'

Test #34:

score: 0
Accepted
time: 501ms
memory: 4596kb

input:

200
142995073 31533364 222440292 437343098 200608122 112797920 416648591 111140409 465296473 88817753 203636174 32196247 376835957 144180359 3311827 201059337 263822500 291784154 50732225 206377725 354894774 155632901 400986304 344353478 23359840 175680456 131191070 208359517 1067584 38809536 307129...

output:

254443070

result:

ok single line: '254443070'

Test #35:

score: 0
Accepted
time: 70ms
memory: 4408kb

input:

200
567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 33734 33735 33736 33737 33738 33739 33740 33741 33742 33743 33744 33745 33746 33747 33748 33749 33750 33751 33752 33753 33754 33755 33756 33757 33758 33759 33760 33761 33762 33763 33764 33765 33766 33767 33768 33769 3377...

output:

17622

result:

ok single line: '17622'

Test #36:

score: 0
Accepted
time: 170ms
memory: 4408kb

input:

200
567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 25934 25935 25936 25937 25938 25939 25940 25941 25942 25943 25944 25945 25946 25947 25948 25949 2595...

output:

14757

result:

ok single line: '14757'

Test #37:

score: 0
Accepted
time: 270ms
memory: 4444kb

input:

200
997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056...

output:

25567

result:

ok single line: '25567'

Test #38:

score: 0
Accepted
time: 315ms
memory: 4736kb

input:

200
666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 ...

output:

16180

result:

ok single line: '16180'