QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#484059 | #5164. 建造军营 | weiguoliang | 100 ✓ | 192ms | 134468kb | C++14 | 2.1kb | 2024-07-19 15:42:46 | 2024-07-19 15:42:48 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define mod 1000000007ll
using namespace std;
struct node{
ll t,n;
}edge[N<<2];
ll head[N],cn=-1,n,m,dfn[N],low[N],cnt=0,nt=0,ji[N],siz[N],dp[N][2],er[N<<1],e[N],sum[N],ans;
bool vis[N];
stack<ll>s;
vector<ll>v[N];
ll read(){char c=getchar();
ll n=0;
while(c<'0'||c>'9')c=getchar();
while(c<='9'&&c>='0')n=(n<<1)+(n<<3)+c-'0',c=getchar();
return n;
}
void add(ll a,ll b){
edge[++cn]={b,head[a]};
head[a]=cn;
}
void tarjan(ll f,ll la){
dfn[f]=low[f]=++cnt,s.push(f),vis[f]=true;
for(auto i:v[f]){
if(i==la)continue;
if(!dfn[i])tarjan(i,f),low[f]=min(low[f],low[i]);
else if(vis[i])low[f]=min(low[f],dfn[i]);
}
if(dfn[f]==low[f]){ll t;nt++;
do{
t=s.top(),s.pop();
ji[t]=nt,siz[nt]++,vis[t]=false;
}while(t!=f);
}
}
//dp[i][1/0]表示第i个点,强制选到i,子树内有无军营
void dfs(ll f,ll la){ll i;
dp[f][0]=er[e[f]],dp[f][1]=(er[e[f]+siz[f]]-er[e[f]]+mod)%mod;
for(i=head[f];i!=-1;i=edge[i].n){
if(edge[i].t==la)continue;
dfs(edge[i].t,f);
dp[f][1]=(dp[f][0]*dp[edge[i].t][1]%mod+dp[f][1]*(dp[edge[i].t][0]*2+dp[edge[i].t][1])%mod)%mod;
dp[f][0]=dp[f][0]*dp[edge[i].t][0]*2%mod;
}
if(f==1)ans=(ans+dp[f][1])%mod;
else ans=(ans+dp[f][1]*er[sum[1]-sum[f]-1]%mod)%mod;
}
void dfs1(ll f,ll la){sum[f]=e[f];
for(ll i=head[f];i!=-1;i=edge[i].n){
if(edge[i].t==la)continue;
dfs1(edge[i].t,f);
sum[f]+=sum[edge[i].t]+1;
}
}
int main(){ll i,k,x,y;
memset(head,-1,sizeof(head));
n=read(),m=read();
for(i=1;i<=m;i++){x=read(),y=read();
v[x].push_back(y),v[y].push_back(x);
}
tarjan(1,0);er[0]=1;
for(i=1;i<=n+m;i++)er[i]=er[i-1]*2ll%mod;
for(i=1;i<=n;i++){
for(auto k:v[i]){
if(ji[k]!=ji[i])add(ji[k],ji[i]);
else e[ji[i]]++;
}
}
for(i=1;i<=nt;i++)e[i]>>=1;
dfs1(1,0);
dfs(1,0);
cout<<ans;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 35940kb
input:
8 8 1 5 5 4 4 1 7 8 3 7 6 3 1 3 2 3
output:
11648
result:
ok 1 number(s): "11648"
Test #2:
score: 5
Accepted
time: 3ms
memory: 34472kb
input:
8 8 6 8 8 4 4 6 7 2 1 7 3 1 4 7 5 8
output:
11776
result:
ok 1 number(s): "11776"
Test #3:
score: 5
Accepted
time: 6ms
memory: 34732kb
input:
8 9 5 6 6 4 4 5 5 3 3 2 2 5 8 1 7 8 4 7
output:
41984
result:
ok 1 number(s): "41984"
Test #4:
score: 5
Accepted
time: 0ms
memory: 35456kb
input:
16 20 2 12 12 14 14 2 2 7 7 11 11 2 15 1 1 4 4 15 15 9 9 16 16 15 15 10 10 3 3 15 13 6 8 13 11 8 9 2 5 1
output:
197767112
result:
ok 1 number(s): "197767112"
Test #5:
score: 5
Accepted
time: 0ms
memory: 35536kb
input:
16 19 9 4 4 7 7 9 9 8 8 13 13 9 9 5 5 16 16 9 9 11 11 14 14 9 15 6 2 15 8 2 10 16 1 10 12 1 3 12
output:
16935922
result:
ok 1 number(s): "16935922"
Test #6:
score: 5
Accepted
time: 0ms
memory: 36076kb
input:
16 18 6 7 7 3 3 6 1 15 15 4 4 1 1 13 13 16 16 1 12 11 5 12 2 5 8 2 14 8 10 14 7 10 16 14 9 7
output:
220856320
result:
ok 1 number(s): "220856320"
Test #7:
score: 5
Accepted
time: 3ms
memory: 36192kb
input:
16 19 11 10 10 16 16 11 11 2 2 3 3 11 12 14 14 15 15 12 7 5 5 8 8 7 6 13 9 6 3 9 4 3 1 4 12 1 8 14
output:
849084416
result:
ok 1 number(s): "849084416"
Test #8:
score: 5
Accepted
time: 8ms
memory: 35332kb
input:
2955 4192 216 639 639 1387 1387 216 216 2383 2383 2654 2654 216 216 2210 2210 2605 2605 216 216 2742 2742 2655 2655 2940 2940 593 593 552 552 510 510 1057 1057 965 965 1780 1780 837 837 2254 2254 1892 1892 2545 2545 2401 2401 1750 1750 321 321 2050 2050 1086 1086 528 528 1701 1701 538 538 2704 2704 ...
output:
489689490
result:
ok 1 number(s): "489689490"
Test #9:
score: 5
Accepted
time: 0ms
memory: 35548kb
input:
2945 4099 1849 1337 1337 169 169 1849 1849 1074 1074 736 736 1849 1849 812 812 1854 1854 1849 1849 1659 1659 1799 1799 1271 1271 351 351 265 265 2619 2619 1021 1021 862 862 1317 1317 1951 1951 1816 1816 1353 1353 706 706 2486 2486 1776 1776 2693 2693 258 258 252 252 2030 2030 1524 1524 490 490 2372 ...
output:
838590971
result:
ok 1 number(s): "838590971"
Test #10:
score: 5
Accepted
time: 91ms
memory: 133108kb
input:
499759 499758 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
454043638
result:
ok 1 number(s): "454043638"
Test #11:
score: 5
Accepted
time: 89ms
memory: 134468kb
input:
499934 499933 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
363824240
result:
ok 1 number(s): "363824240"
Test #12:
score: 5
Accepted
time: 177ms
memory: 114468kb
input:
499910 499909 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
595142370
result:
ok 1 number(s): "595142370"
Test #13:
score: 5
Accepted
time: 177ms
memory: 113648kb
input:
497434 497433 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
672159037
result:
ok 1 number(s): "672159037"
Test #14:
score: 5
Accepted
time: 161ms
memory: 115836kb
input:
498594 498593 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
730193382
result:
ok 1 number(s): "730193382"
Test #15:
score: 5
Accepted
time: 156ms
memory: 113480kb
input:
491691 491691 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
178453330
result:
ok 1 number(s): "178453330"
Test #16:
score: 5
Accepted
time: 150ms
memory: 111140kb
input:
494909 494909 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 ...
output:
189917991
result:
ok 1 number(s): "189917991"
Test #17:
score: 5
Accepted
time: 192ms
memory: 86792kb
input:
496680 669728 278429 179810 179810 78114 78114 278429 278429 263631 263631 473590 473590 278429 278429 400998 400998 478024 478024 278429 278429 411923 411923 316261 316261 361842 361842 131858 131858 62950 62950 374524 374524 354457 354457 159387 159387 84068 84068 468583 468583 281544 281544 21024...
output:
558341955
result:
ok 1 number(s): "558341955"
Test #18:
score: 5
Accepted
time: 168ms
memory: 85736kb
input:
492468 674661 172895 370268 370268 72327 72327 172895 172895 83421 83421 56710 56710 172895 172895 91556 91556 487022 487022 172895 172895 301253 301253 471820 471820 186463 186463 219659 219659 222758 222758 475707 475707 198110 198110 112885 112885 87509 87509 417623 417623 183964 183964 179360 17...
output:
956578065
result:
ok 1 number(s): "956578065"
Test #19:
score: 5
Accepted
time: 182ms
memory: 84292kb
input:
495531 685632 363871 199154 199154 290146 290146 363871 363871 285706 285706 181450 181450 363871 363871 57397 57397 246929 246929 363871 363871 100675 100675 161126 161126 348991 348991 51059 51059 187343 187343 178826 178826 214135 214135 77835 77835 49971 49971 313842 313842 378994 378994 324892 ...
output:
393159589
result:
ok 1 number(s): "393159589"
Test #20:
score: 5
Accepted
time: 190ms
memory: 91544kb
input:
492842 688856 407751 199116 199116 305848 305848 407751 407751 237041 237041 241971 241971 407751 407751 122561 122561 220589 220589 407751 407751 187952 187952 16432 16432 215452 215452 411729 411729 406334 406334 338946 338946 113993 113993 211645 211645 80319 80319 159214 159214 335495 335495 231...
output:
637387455
result:
ok 1 number(s): "637387455"
Extra Test:
score: 0
Extra Test Passed