QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#184234#2893. 独立2023zllAC ✓169ms12092kbC++142.6kb2023-09-20 15:29:272023-09-20 15:29:27

Judging History

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

  • [2023-09-20 15:29:27]
  • 评测
  • 测评结果:AC
  • 用时:169ms
  • 内存:12092kb
  • [2023-09-20 15:29:27]
  • 提交

answer

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
typedef long long ll;
const int maxn=100000,maxm=50000,maxk=10,q=101,b=137,p=1000000007;
int n,m,_x,_y,_a,_z;
std::set<std::pair<int,int>>E;
template<const int maxnode,const int maxedge>
struct Graph{
	int head[maxnode+1],total;
	struct Edge{
		int to,next,len;
	}e[maxedge+1];
	void add(const int u,const int v,const int w){
		e[++total]=Edge{v,head[u],w};
		head[u]=total;
	}
};
Graph<maxn,maxm*2>G;
Graph<maxn,maxm>T;
int w[maxn+1];
ll f[maxn+1],g[maxn+1];
int node[maxn+1],vis_cnt;
char vis[maxn+1];
void dfs_1(const int u){
	node[++vis_cnt]=u;
	vis[u]='1';
	for(int i=G.head[u];i;i=G.e[i].next){
		const int v=G.e[i].to;
		if(vis[v]=='0')dfs_1(v);
	}
}
void dfs_2(const int u){
	vis[u]='4';
	for(int i=G.head[u];i;i=G.e[i].next){
		const int v=G.e[i].to;
		if(vis[v]=='2'){
			T.add(u,v,G.e[i].len);
			dfs_2(v);
		}
	}
}
int rt[maxn+1],rt_cnt;
int special_id[maxn+1],special[maxk],k;
void dfs_3(const int u){
	for(int i=T.head[u];i;i=T.e[i].next){
		const int v=T.e[i].to;
		dfs_3(v);
		f[u]+=std::max(f[v]-T.e[i].len,g[v]);
		g[u]+=std::max(f[v],g[v]);
	}
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&_x,&_y,&_a,&_z);
	for(int i=1;i<=n;i++){
		_a=((ll)q*_a+b)%p;
		w[i]=_a;
	}
	for(int i=1,x,y;i<=m;i++){
		_x=((ll)q*_x+b)%p;
		_y=((ll)q*_y+b)%p;
		_z=((ll)q*_z+b)%p;
		x=_x%n+1,y=_y%n+1;
		if(x==y||E.find({x,y})!=E.end()||E.find({y,x})!=E.end())continue;
		E.emplace(x,y);
		G.add(x,y,_z),G.add(y,x,_z);
	}
	memset(vis+1,'0',sizeof(char)*n);
	memset(special_id+1,-1,sizeof(int)*n);
	for(int _=1;_<=n;_++)
		if(vis[_]=='0'){
			vis_cnt=0;
			dfs_1(_);
			for(int i=1;i<=vis_cnt;i++){
				const int u=node[i];
				int f=0;
				for(int i=G.head[u];i;i=G.e[i].next){
					const int v=G.e[i].to;
					if(vis[v]=='2'){
						if(!f)f=v;
						else{
							f=-1;
							special_id[u]=k;
							special[k++]=u;
							vis[u]='3';
						}
					}
				}
				if(vis[u]=='1')vis[u]='2';
			}
		}
	for(int _=1;_<=n;_++)
		if(vis[_]=='2'){
			dfs_2(_);
			rt[++rt_cnt]=_;
		}
	ll res=0;
	for(int S=0;S<(1<<k);S++){
		ll ans=0;
		for(int u=1;u<=n;u++)f[u]=w[u];
		memset(g+1,0,sizeof(ll)*n);
		for(int i=0;i<k;i++)
			if((S>>i)&1){
				const int u=special[i];
				ans+=w[u];
				for(int i=G.head[u];i;i=G.e[i].next){
					const int v=G.e[i].to;
					if(special_id[v]==-1)f[v]-=G.e[i].len;
					else if(special_id[u]<special_id[v]&&((S>>special_id[v])&1))ans-=G.e[i].len;
				}
			}
		for(int i=1;i<=rt_cnt;i++){
			dfs_3(rt[i]);
			ans+=std::max(f[rt[i]],g[rt[i]]);
		}
		res=std::max(res,ans);
	}
	printf("%lld\n",res);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10 5 1 2 3 4

output:

3909327860

result:

ok single line: '3909327860'

Test #2:

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

input:

10000 5000 323944114 980712849 218464573 902936457

output:

4127316482561

result:

ok single line: '4127316482561'

Test #3:

score: 0
Accepted
time: 38ms
memory: 11512kb

input:

100000 50000 69108640 163256243 729156747 674884157

output:

40985622819672

result:

ok single line: '40985622819672'

Test #4:

score: 0
Accepted
time: 30ms
memory: 11984kb

input:

100000 50000 274087387 315287350 284117614 889718361

output:

40947902019309

result:

ok single line: '40947902019309'

Test #5:

score: 0
Accepted
time: 26ms
memory: 11960kb

input:

100000 50000 626549769 467318457 986562122 104552559

output:

40907099503987

result:

ok single line: '40907099503987'

Test #6:

score: 0
Accepted
time: 25ms
memory: 11508kb

input:

100000 50000 831528516 619349564 689006624 319386763

output:

41017978988200

result:

ok single line: '41017978988200'

Test #7:

score: 0
Accepted
time: 30ms
memory: 11508kb

input:

100000 50000 36507256 771380671 243967491 534220967

output:

41077280523359

result:

ok single line: '41077280523359'

Test #8:

score: 0
Accepted
time: 37ms
memory: 11476kb

input:

100000 50000 388969637 923411777 946411999 749055172

output:

41009748953373

result:

ok single line: '41009748953373'

Test #9:

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

input:

100000 50000 593948384 75442877 648856501 963889376

output:

40991206034855

result:

ok single line: '40991206034855'

Test #10:

score: 0
Accepted
time: 29ms
memory: 12088kb

input:

100000 50000 946410766 227473984 203817368 31239940

output:

40932441913184

result:

ok single line: '40932441913184'

Test #11:

score: 0
Accepted
time: 169ms
memory: 11456kb

input:

100000 50000 663698625 561638538 539101941 150346545

output:

40924699056938

result:

ok single line: '40924699056938'

Test #12:

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

input:

6 3 90677470 927115294 683528073 970379897

output:

2137516189

result:

ok single line: '2137516189'

Test #13:

score: 0
Accepted
time: 32ms
memory: 11516kb

input:

100000 50000 713669645 241546443 365180750 489471924

output:

40894915891391

result:

ok single line: '40894915891391'

Test #14:

score: 0
Accepted
time: 31ms
memory: 12040kb

input:

100000 50000 221139747 865700752 943990951 580014954

output:

40816659887937

result:

ok single line: '40816659887937'

Test #15:

score: 0
Accepted
time: 37ms
memory: 11592kb

input:

100000 50000 426118494 17731852 498951818 794849159

output:

41067804257367

result:

ok single line: '41067804257367'

Test #16:

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

input:

100000 50000 778580875 169762958 201396320 57380682

output:

41019991719429

result:

ok single line: '41019991719429'

Test #17:

score: 0
Accepted
time: 32ms
memory: 12044kb

input:

100000 50000 983559622 321794065 903840828 77033926

output:

41056783133409

result:

ok single line: '41056783133409'

Test #18:

score: 0
Accepted
time: 30ms
memory: 12092kb

input:

100000 50000 188538363 473825172 458801695 291868131

output:

40983981734650

result:

ok single line: '40983981734650'

Test #19:

score: 0
Accepted
time: 26ms
memory: 11808kb

input:

100000 50000 541000744 625856279 161246197 506702335

output:

41007858745216

result:

ok single line: '41007858745216'

Test #20:

score: 0
Accepted
time: 21ms
memory: 11392kb

input:

100000 50000 745979491 777887386 863690705 721536540

output:

41012305119617

result:

ok single line: '41012305119617'

Test #21:

score: 0
Accepted
time: 43ms
memory: 11380kb

input:

100000 50000 929918492 418651573 936370744 288067408

output:

40948033429862

result:

ok single line: '40948033429862'

Test #22:

score: 0
Accepted
time: 42ms
memory: 11488kb

input:

100000 50000 815729732 264083040 753936146 558134119

output:

41103051884986

result:

ok single line: '41103051884986'

Test #23:

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

input:

6 3 517823605 849894548 121910581 290446313

output:

2830036710

result:

ok single line: '2830036710'

Test #24:

score: 0
Accepted
time: 31ms
memory: 11944kb

input:

100000 50000 20708472 416114146 456380647 122827913

output:

41018143959974

result:

ok single line: '41018143959974'

Test #25:

score: 0
Accepted
time: 26ms
memory: 11688kb

input:

100000 50000 373170854 568145253 11341514 337662118

output:

41028863217493

result:

ok single line: '41028863217493'

Test #26:

score: 0
Accepted
time: 35ms
memory: 11520kb

input:

100000 50000 578149601 720176360 713786023 552496322

output:

40951181028791

result:

ok single line: '40951181028791'

Test #27:

score: 0
Accepted
time: 26ms
memory: 11456kb

input:

100000 50000 930611982 872207467 416230524 767330526

output:

40948576487909

result:

ok single line: '40948576487909'

Test #28:

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

input:

100000 50000 135590722 982164731 788820845 353029936

output:

41020594313888

result:

ok single line: '41020594313888'

Test #29:

score: 0
Accepted
time: 29ms
memory: 11900kb

input:

100000 50000 340569469 28786039 673635900 196998928

output:

41035989067161

result:

ok single line: '41035989067161'

Test #30:

score: 0
Accepted
time: 34ms
memory: 11356kb

input:

100000 50000 693031851 180817146 376080401 411833133

output:

41069115335862

result:

ok single line: '41069115335862'

Test #31:

score: 0
Accepted
time: 26ms
memory: 11324kb

input:

100000 50000 898010598 332848253 626667337 356729603

output:

41076889170221

result:

ok single line: '41076889170221'

Test #32:

score: 0
Accepted
time: 56ms
memory: 11784kb

input:

100000 50000 102989338 484879360 633485777 841501541

output:

41126348825706

result:

ok single line: '41126348825706'

Test #33:

score: 0
Accepted
time: 31ms
memory: 11364kb

input:

100000 50000 967760839 966527548 968770350 813124513

output:

40963659647260

result:

ok single line: '40963659647260'

Test #34:

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

input:

10 5 335727704 87288204 547385244 288081467

output:

3351218817

result:

ok single line: '3351218817'

Test #35:

score: 0
Accepted
time: 24ms
memory: 11428kb

input:

100000 50000 172739579 671214851 27958710 289574275

output:

41023167425732

result:

ok single line: '41023167425732'

Test #36:

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

input:

100000 50000 525201960 123106121 226175719 242792915

output:

40939293482589

result:

ok single line: '40939293482589'

Test #37:

score: 0
Accepted
time: 19ms
memory: 11384kb

input:

100000 50000 730180708 275137227 928620227 457627119

output:

41116772147109

result:

ok single line: '41116772147109'

Test #38:

score: 0
Accepted
time: 26ms
memory: 11712kb

input:

100000 50000 427168334 631064729 672461324 857483040

output:

41025540909037

result:

ok single line: '41025540909037'

Test #39:

score: 0
Accepted
time: 33ms
memory: 12048kb

input:

100000 50000 287621829 579199441 186025596 887295528

output:

41041606108852

result:

ok single line: '41041606108852'

Test #40:

score: 0
Accepted
time: 29ms
memory: 11900kb

input:

100000 50000 492600576 731230548 888470104 520261001

output:

41050863684028

result:

ok single line: '41050863684028'

Test #41:

score: 0
Accepted
time: 34ms
memory: 11392kb

input:

100000 50000 845062957 883261655 590914606 169480296

output:

41064379595552

result:

ok single line: '41064379595552'

Test #42:

score: 0
Accepted
time: 29ms
memory: 11464kb

input:

100000 50000 50041698 35292754 145875473 384314500

output:

40994165715249

result:

ok single line: '40994165715249'

Test #43:

score: 0
Accepted
time: 29ms
memory: 11980kb

input:

100000 50000 255020445 187323861 848319981 599148705

output:

41015913407828

result:

ok single line: '41015913407828'

Test #44:

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

input:

100000 0 1 2 3 4

output:

49891211697278

result:

ok single line: '49891211697278'

Test #45:

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

input:

100 50 499308315 298486660 933836775 591606674

output:

40654051506

result:

ok single line: '40654051506'

Test #46:

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

input:

100000 50000 1 1 2 3

output:

49965403577651

result:

ok single line: '49965403577651'

Test #47:

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

input:

100 50 85174457 766036718 917683570 796585422

output:

38414656729

result:

ok single line: '38414656729'

Test #48:

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

input:

1000 500 187537858 256543968 335220000 244298843

output:

404321266633

result:

ok single line: '404321266633'

Test #49:

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

input:

1000 500 655087915 92907130 687682381 396329949

output:

400275637877

result:

ok single line: '400275637877'

Test #50:

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

input:

10000 5000 340097318 775734102 66433466 200491948

output:

4124854860192

result:

ok single line: '4124854860192'