QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#184234 | #2893. 独立 | 2023zll | AC ✓ | 169ms | 12092kb | C++14 | 2.6kb | 2023-09-20 15:29:27 | 2023-09-20 15:29:27 |
Judging History
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'