QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#484059#5164. 建造军营weiguoliang100 ✓192ms134468kbC++142.1kb2024-07-19 15:42:462024-07-19 15:42:48

Judging History

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

  • [2024-07-19 15:42:48]
  • 评测
  • 测评结果:100
  • 用时:192ms
  • 内存:134468kb
  • [2024-07-19 15:42:46]
  • 提交

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