QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#258506#7794. 水果茶zhouhuanyi100 ✓923ms1775012kbC++144.4kb2023-11-19 19:23:282023-11-19 19:23:29

Judging History

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

  • [2023-11-19 19:23:29]
  • 评测
  • 测评结果:100
  • 用时:923ms
  • 内存:1775012kb
  • [2023-11-19 19:23:28]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<stack>
#include<random>
#define N 6000000
#define mod 1315105
using namespace std;
const int inf=(int)(1e9);
char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
inline int read(){
    int aa;
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';
    return aa;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int n,m,k,ans,seed,length,leng,lengs,a[N+1],dfn[N+1],dfns[N+1],low[N+1],F[N+1],G[N+1],delta[N+1];
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<int>dp[N+1];
stack<int>p;
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++leng,p.push(x);
	for (int i=0;i<E[x].size();++i)
	{
		if (!dfn[E[x][i]])
		{
			tarjan(E[x][i]),low[x]=min(low[x],low[E[x][i]]);
			if (low[E[x][i]]>=dfn[x])
			{
				if (p.top()==E[x][i]) ES[x].push_back(E[x][i]),p.pop();
				else
				{
					++length,ES[x].push_back(length);
					while (p.top()!=E[x][i]) ES[length].push_back(p.top()),p.pop();
					ES[length].push_back(p.top()),p.pop();
				}
			}
		}
		else low[x]=min(low[x],dfn[E[x][i]]);
	}
	return;
}
void merge(int x,int y)
{
	if (dp[x].size()>dp[y].size()) swap(dp[x],dp[y]);
	for (int i=0;i<dp[x].size();++i)
		if (0<=k-i&&k-i<dp[y].size())
			Adder(ans,1ll*dp[x][dp[x].size()-1-i]*dp[y][dp[y].size()-1-(k-i)]%mod);
	for (int i=0;i<dp[x].size();++i) Adder(dp[y][dp[y].size()-1-i],dp[x][dp[x].size()-1-i]);
	dp[x].shrink_to_fit();
	return;
}
void dfs(int x)
{
	int maxn=0,maxer=0,rt=0,smaxn=0,srt=0,len,d,ds,ps;
	if (x<=n)
	{
		dp[x]={a[x]};
		for (int i=0;i<ES[x].size();++i)
		{
			dfs(ES[x][i]);
			if (ES[x][i]<=n) dp[ES[x][i]].push_back(0);
			merge(ES[x][i],x);
		}
	}
	else
	{
		len=ES[x].size()+1;
		for (int i=0;i<ES[x].size();++i)
		{
			dfs(ES[x][i]);
			if (dp[ES[x][i]].size()>maxn) maxn=dp[ES[x][i]].size(),maxer=ES[x][i],rt=i;
		}
		for (int i=0;i<ES[x].size();++i)
			if (i!=rt)
			{
			    for (int j=0;j<dp[ES[x][i]].size();++j)
				{
					d=k-j-min(abs(rt-i),len-abs(rt-i));
					if (0<=d&&d<maxn) Adder(ans,1ll*dp[ES[x][i]][dp[ES[x][i]].size()-1-j]*dp[maxer][maxn-1-d]%mod);
				}
			}
		ps=-1;
		for (int i=0;i<ES[x].size();++i)
		{
			while (((i-(ps+1))<<1)>ES[x].size())
			{
				++ps;
				if (ps!=rt)
				{
					for (int j=0;j<dp[ES[x][ps]].size();++j) Adder(F[j+ps],dp[ES[x][ps]][dp[ES[x][ps]].size()-1-j]),Adder2(G[j+ES[x].size()-1-ps],-dp[ES[x][ps]][dp[ES[x][ps]].size()-1-j]);
				}
			}
			if (i!=rt)
			{
				for (int j=0;j<dp[ES[x][i]].size();++j)
				{
					if (k-j+i-len>=0) Adder(ans,1ll*dp[ES[x][i]][dp[ES[x][i]].size()-1-j]*F[k-j+i-len]%mod);
					if (k-j+ES[x].size()-1-i>=0) Adder(ans,1ll*dp[ES[x][i]][dp[ES[x][i]].size()-1-j]*G[k-j+ES[x].size()-1-i]%mod);
				}
				for (int j=0;j<dp[ES[x][i]].size();++j) Adder(G[j+ES[x].size()-1-i],dp[ES[x][i]][dp[ES[x][i]].size()-1-j]);
			}
		}
		for (int i=0;i<ES[x].size();++i)
			if (i!=rt)
			{
				if (i<=ps)
				{
					for (int j=0;j<dp[ES[x][i]].size();++j) F[j+i]=0;
				}
				else
				{
					for (int j=0;j<dp[ES[x][i]].size();++j) G[j+ES[x].size()-1-i]=0;
				}
			}
		for (int i=0;i<ES[x].size();++i)
			if (dp[ES[x][i]].size()+min(i+1,(int)(ES[x].size())-i)>smaxn)
				smaxn=dp[ES[x][i]].size()+min(i+1,(int)(ES[x].size())-i),srt=i;
		if (srt!=rt)
		{
			dp[x].resize(smaxn);
			for (int i=0;i<ES[x].size();++i)
			{
				for (int j=0;j<dp[ES[x][i]].size();++j) d=j+min(i+1,(int)(ES[x].size())-i),Adder(dp[x][dp[x].size()-1-d],dp[ES[x][i]][dp[ES[x][i]].size()-1-j]);
			}
		}
		else
		{
			ds=smaxn-dp[maxer].size(),swap(dp[x],dp[maxer]);
			for (int i=1;i<=ds;++i) dp[x].push_back(0);
			for (int i=0;i<ES[x].size();++i)
				if (i!=rt)
				{
					for (int j=0;j<dp[ES[x][i]].size();++j) d=j+min(i+1,(int)(ES[x].size())-i),Adder(dp[x][dp[x].size()-1-d],dp[ES[x][i]][dp[ES[x][i]].size()-1-j]);
				}
		}
	}
	for (int i=0;i<ES[x].size();++i) dp[ES[x][i]].shrink_to_fit();
	return;
}
int main()
{
	int x,y;
	length=n=read(),m=read(),k=read();
	for (int i=1;i<=m;++i) x=read(),y=read(),add(x,y);
	seed=read();
	mt19937_64 rnd(seed);
	for (int i=1;i<=n;++i) a[i]=(rnd()%inf+1)%mod;
	tarjan(1),dfs(1),printf("%d\n",ans);
	return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 50ms
memory: 436232kb

input:

3000 3408 93
1 2
2 3
3 4
4 5
1 6
3 7
6 8
7 9
6 10
6 11
11 12
12 13
9 14
12 15
13 16
15 17
15 18
18 19
15 20
18 21
20 22
18 23
22 24
23 25
23 26
26 27
27 28
27 29
29 30
26 31
27 32
29 33
32 34
30 35
32 36
36 37
37 38
35 39
39 40
37 41
37 42
41 43
39 44
41 45
45 46
45 47
46 48
48 49
47 50
47 51
51 52
...

output:

929234

result:

ok 1 number(s): "929234"

Test #2:

score: 0
Accepted
time: 52ms
memory: 433144kb

input:

3000 3404 8
1 2
1 3
1 4
4 5
4 6
2 7
4 8
5 9
8 10
10 11
9 12
12 13
9 14
11 15
13 16
15 17
16 18
15 19
17 20
18 21
21 22
19 23
21 24
24 25
24 26
25 27
26 28
27 29
27 30
26 31
31 32
28 33
30 34
30 35
32 36
35 37
34 38
34 39
36 40
39 41
39 42
42 43
39 44
44 45
44 46
42 47
45 48
47 49
46 50
46 51
51 52
4...

output:

700402

result:

ok 1 number(s): "700402"

Test #3:

score: 0
Accepted
time: 46ms
memory: 432624kb

input:

2928 3260 15
1 2
1 3
1 4
4 5
2 6
1 7
1 8
2 9
9 10
6 11
8 12
3 13
6 14
11 15
3 16
1 17
16 18
7 19
6 20
1 21
3 22
18 23
4 24
11 25
19 26
21 27
15 28
1 29
18 30
25 31
27 32
18 33
29 34
33 35
16 36
13 37
19 38
13 39
18 40
18 41
34 42
28 43
42 44
4 45
22 46
28 47
36 48
46 49
12 50
39 51
15 52
5 53
45 54
...

output:

563777

result:

ok 1 number(s): "563777"

Test #4:

score: 0
Accepted
time: 44ms
memory: 433784kb

input:

2935 3257 17
1 2
1 3
2 4
4 5
5 6
4 7
7 8
8 9
7 10
10 11
4 12
1 13
4 14
1 15
3 16
7 17
14 18
10 19
15 20
20 21
7 22
4 23
14 24
7 25
22 26
22 27
4 28
11 29
13 30
11 31
23 32
32 33
22 34
31 35
10 36
11 37
25 38
8 39
30 40
6 41
1 42
4 43
18 44
28 45
11 46
11 47
14 48
42 49
36 50
28 51
15 52
16 53
18 54
...

output:

1076031

result:

ok 1 number(s): "1076031"

Test #5:

score: 0
Accepted
time: 57ms
memory: 433288kb

input:

2789 3104 17
1 2
2 3
3 4
4 5
4 6
3 7
2 8
6 9
2 10
6 11
8 12
3 13
5 14
11 15
4 16
12 17
13 18
15 19
6 20
9 21
17 22
20 23
23 24
20 25
17 26
13 27
11 28
2 29
16 30
12 31
21 32
16 33
33 34
14 35
22 36
12 37
37 38
31 39
32 40
12 41
4 42
42 43
18 44
29 45
23 46
19 47
35 48
47 49
34 50
17 51
29 52
13 53
4...

output:

1030647

result:

ok 1 number(s): "1030647"

Test #6:

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

input:

2773 3068 5
1 2
1 3
1 4
3 5
5 6
1 7
6 8
3 9
3 10
10 11
9 12
5 13
9 14
4 15
9 16
11 17
1 18
11 19
17 20
17 21
16 22
4 23
23 24
22 25
12 26
18 27
17 28
21 29
16 30
3 31
29 32
9 33
6 34
9 35
28 36
3 37
31 38
18 39
10 40
23 41
15 42
4 43
12 44
41 45
11 46
3 47
11 48
19 49
25 50
11 51
2 52
24 53
42 54
17...

output:

1019285

result:

ok 1 number(s): "1019285"

Test #7:

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

input:

2756 3058 17
1 2
2 3
3 4
3 5
1 6
6 7
1 8
3 9
2 10
2 11
11 12
12 13
13 14
14 15
5 16
16 17
5 18
10 19
14 20
18 21
17 22
22 23
9 24
7 25
11 26
19 27
12 28
1 29
6 30
4 31
25 32
5 33
23 34
1 35
11 36
1 37
35 38
34 39
32 40
12 41
20 42
12 43
31 44
1 45
34 46
20 47
3 48
44 49
27 50
2 51
35 52
34 53
53 54
...

output:

664550

result:

ok 1 number(s): "664550"

Subtask #2:

score: 10
Accepted

Test #8:

score: 10
Accepted
time: 75ms
memory: 443636kb

input:

99734 99733 32
1 2
1 3
2 4
3 5
4 6
5 7
5 8
5 9
4 10
8 11
10 12
2 13
5 14
14 15
11 16
11 17
1 18
5 19
9 20
16 21
20 22
1 23
23 24
5 25
24 26
25 27
1 28
3 29
15 30
14 31
24 32
3 33
29 34
31 35
11 36
9 37
30 38
4 39
26 40
3 41
25 42
36 43
34 44
43 45
13 46
42 47
5 48
48 49
14 50
30 51
2 52
47 53
53 54
...

output:

1163399

result:

ok 1 number(s): "1163399"

Test #9:

score: 0
Accepted
time: 84ms
memory: 440308kb

input:

99986 99985 77
1 2
2 3
3 4
1 5
3 6
6 7
3 8
6 9
7 10
7 11
9 12
4 13
2 14
6 15
3 16
16 17
15 18
5 19
19 20
7 21
13 22
5 23
22 24
24 25
22 26
9 27
26 28
10 29
18 30
29 31
19 32
17 33
23 34
30 35
11 36
32 37
34 38
27 39
32 40
38 41
18 42
28 43
43 44
2 45
7 46
28 47
10 48
34 49
9 50
18 51
33 52
32 53
3 5...

output:

954238

result:

ok 1 number(s): "954238"

Test #10:

score: 0
Accepted
time: 86ms
memory: 443404kb

input:

99712 99711 27
1 2
2 3
3 4
1 5
4 6
3 7
6 8
8 9
3 10
3 11
10 12
5 13
8 14
4 15
13 16
12 17
6 18
11 19
16 20
14 21
15 22
14 23
23 24
22 25
21 26
25 27
11 28
8 29
21 30
6 31
3 32
25 33
14 34
9 35
15 36
27 37
10 38
24 39
20 40
17 41
4 42
15 43
21 44
16 45
36 46
28 47
12 48
42 49
41 50
30 51
20 52
3 53
2...

output:

328290

result:

ok 1 number(s): "328290"

Test #11:

score: 0
Accepted
time: 72ms
memory: 443852kb

input:

99923 99922 587
1 2
2 3
2 4
1 5
3 6
6 7
3 8
6 9
6 10
2 11
7 12
11 13
7 14
14 15
7 16
8 17
17 18
13 19
17 20
9 21
11 22
11 23
21 24
7 25
25 26
21 27
17 28
5 29
4 30
14 31
1 32
10 33
33 34
7 35
19 36
30 37
15 38
21 39
11 40
39 41
1 42
10 43
33 44
33 45
44 46
44 47
15 48
16 49
40 50
18 51
2 52
17 53
6 ...

output:

271483

result:

ok 1 number(s): "271483"

Test #12:

score: 0
Accepted
time: 69ms
memory: 457688kb

input:

99877 99876 506
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
5...

output:

642658

result:

ok 1 number(s): "642658"

Subtask #3:

score: 10
Accepted

Test #13:

score: 10
Accepted
time: 72ms
memory: 445788kb

input:

100000 100000 229
1 2
2 3
1 4
2 5
1 6
4 7
3 8
3 9
7 10
6 11
2 12
10 13
12 14
5 15
7 16
9 17
16 18
13 19
13 20
15 21
14 22
14 23
16 24
22 25
16 26
17 27
22 28
27 29
28 30
30 31
24 32
29 33
30 34
26 35
32 36
32 37
30 38
37 39
35 40
31 41
32 42
38 43
36 44
35 45
40 46
40 47
42 48
47 49
46 50
48 51
46 5...

output:

910558

result:

ok 1 number(s): "910558"

Subtask #4:

score: 10
Accepted

Test #14:

score: 10
Accepted
time: 67ms
memory: 436928kb

input:

89874 89894 91
1 2
2 3
2 4
1 5
4 6
1 7
5 8
8 9
6 10
7 11
10 12
1 13
10 14
3 15
13 16
11 17
15 18
4 19
7 20
13 21
3 22
15 23
14 24
16 25
14 26
22 27
7 28
1 29
10 30
26 31
28 32
5 33
7 34
15 35
20 36
34 37
16 38
18 39
24 40
13 41
17 42
26 43
18 44
21 45
42 46
41 47
3 48
46 49
34 50
17 51
22 52
10 53
3...

output:

1049004

result:

ok 1 number(s): "1049004"

Subtask #5:

score: 20
Accepted

Test #15:

score: 20
Accepted
time: 76ms
memory: 444592kb

input:

90000 93021 19
1 2
1 3
3 4
1 5
3 6
5 7
5 8
5 9
4 10
5 11
3 12
7 13
10 14
5 15
6 16
9 17
8 18
16 19
17 20
12 21
20 22
22 23
15 24
22 25
22 26
19 27
26 28
27 29
22 30
29 31
23 32
28 33
32 34
26 35
29 36
36 37
28 38
36 39
36 40
34 41
33 42
35 43
41 44
36 45
40 46
43 47
46 48
39 49
44 50
47 51
46 52
52 ...

output:

618387

result:

ok 1 number(s): "618387"

Subtask #6:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 77ms
memory: 446128kb

input:

89849 95377 39
1 2
2 3
2 4
2 5
4 6
6 7
7 8
4 9
5 10
6 11
2 12
2 13
12 14
1 15
1 16
8 17
12 18
10 19
5 20
9 21
1 22
7 23
23 24
23 25
16 26
26 27
26 28
8 29
25 30
16 31
22 32
14 33
6 34
16 35
11 36
12 37
14 38
13 39
5 40
26 41
1 42
32 43
38 44
31 45
16 46
5 47
29 48
45 49
22 50
50 51
48 52
20 53
33 54...

output:

1122581

result:

ok 1 number(s): "1122581"

Subtask #7:

score: 20
Accepted

Test #17:

score: 20
Accepted
time: 547ms
memory: 717956kb

input:

3000002 4500001 2
2 3
2 1
3 1
4 5
4 1
5 1
6 7
6 1
7 1
8 9
8 1
9 1
10 11
10 1
11 1
12 13
12 1
13 1
14 15
14 1
15 1
16 17
16 1
17 1
18 19
18 1
19 1
20 21
20 1
21 1
22 23
22 1
23 1
24 25
24 1
25 1
26 27
26 1
27 1
28 29
28 1
29 1
30 31
30 1
31 1
32 33
32 1
33 1
34 35
34 1
35 1
36 37
36 1
37 1
38 39
38 1...

output:

527074

result:

ok 1 number(s): "527074"

Test #18:

score: 0
Accepted
time: 923ms
memory: 1775012kb

input:

4999999 5000000 5847
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50...

output:

452257

result:

ok 1 number(s): "452257"

Test #19:

score: 0
Accepted
time: 833ms
memory: 1012824kb

input:

4599847 4639731 37
1 2
2 3
3 4
4 5
1 6
2 7
4 8
4 9
8 10
6 11
11 12
12 13
13 14
14 15
15 16
15 17
17 18
15 19
17 20
17 21
18 22
19 23
23 24
23 25
21 26
23 27
23 28
26 29
26 30
30 31
28 32
32 33
29 34
34 35
35 36
34 37
34 38
37 39
38 40
37 41
41 42
40 43
41 44
41 45
42 46
45 47
44 48
48 49
48 50
48 51...

output:

852791

result:

ok 1 number(s): "852791"

Test #20:

score: 0
Accepted
time: 902ms
memory: 1138812kb

input:

4899913 4940561 923764
1 2
1 3
2 4
1 5
2 6
5 7
3 8
8 9
6 10
9 11
11 12
9 13
9 14
10 15
11 16
12 17
16 18
15 19
16 20
20 21
18 22
18 23
21 24
20 25
24 26
26 27
25 28
25 29
26 30
29 31
29 32
32 33
32 34
32 35
32 36
36 37
34 38
36 39
38 40
36 41
40 42
38 43
42 44
41 45
43 46
42 47
47 48
47 49
45 50
48 ...

output:

501197

result:

ok 1 number(s): "501197"