QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#258506 | #7794. 水果茶 | zhouhuanyi | 100 ✓ | 923ms | 1775012kb | C++14 | 4.4kb | 2023-11-19 19:23:28 | 2023-11-19 19:23:29 |
Judging History
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"