QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#90070	#5357. 芒果冰加了空气	zhouhuanyi	100 ✓	271ms	138184kb	C++23	1.4kb	2023-03-22 09:57:17	2023-03-22 09:57:18

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-22 09:57:18]
评测

测评结果：100
用时：271ms
内存：138184kb

查看

[2023-03-22 09:57:17]
提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 5000
#define mod 1000000007
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
void Adder(int &x,int d)
{
    x+=d;
    if (x>=mod) x-=mod;
    return;
}
int MD(int x)
{
    return x>=mod?x-mod:x;
}
int n,ans,C[N+1][N+1],sz[N+1],dp[N+1][N+1],F[N+1],G[N+1];
vector<int>E[N+1];
bool used[N+1];
void add(int x,int y)
{
    E[x].push_back(y),E[y].push_back(x);
    return;
}
void dfs(int x)
{
    used[x]=sz[x]=dp[x][1]=1;
    for (int i=0;i<E[x].size();++i)
	if (!used[E[x][i]])
	{
	    dfs(E[x][i]);
	    for (int j=1;j<=sz[x]+sz[E[x][i]];++j) F[j]=0;
	    for (int j=0;j<=sz[E[x][i]];++j) G[j]=dp[E[x][i]][j];
	    for (int j=sz[E[x][i]]-1;j>=0;--j) Adder(G[j],G[j+1]);
	    for (int j=1;j<=sz[x];++j)
		for (int k=0;k<=sz[E[x][i]];++k)
		    Adder(F[j+k],1ll*dp[x][j]*G[k]%mod*C[j-1+k][k]%mod);
	    for (int j=1;j<=sz[x]+sz[E[x][i]];++j) dp[x][j]=F[j];
	    sz[x]+=sz[E[x][i]];
	}
    return;
}
int main()
{
    int x,y;
    for (int i=0;i<=N;++i) C[i][0]=1;
    for (int i=1;i<=N;++i)
	for (int j=1;j<=i;++j)
	    C[i][j]=MD(C[i-1][j-1]+C[i-1][j]);
    n=read();
    for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
    dfs(1);
    for (int i=1;i<=n;++i) Adder(ans,dp[1][i]);
    printf("%d\n",ans);
    return 0;
}

源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

详细

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 28ms

memory: 70404kb

input:

output:

result:

ok single line: '310862'

Test #2:

score: 0

Accepted

time: 8ms

memory: 70672kb

input:

output:

result:

ok single line: '64804'

Test #3:

score: 0

Accepted

time: 12ms

memory: 70640kb

input:

output:

result:

ok single line: '258182'

Test #4:

score: 0

Accepted

time: 12ms

memory: 70644kb

input:

output:

result:

ok single line: '16796'

Test #5:

score: 0

Accepted

time: 12ms

memory: 70512kb

input:

output:

result:

ok single line: '78384'

Test #6:

score: 0

Accepted

time: 16ms

memory: 70668kb

input:

output:

result:

ok single line: '38896'

Test #7:

score: 0

Accepted

time: 8ms

memory: 70512kb

input:

output:

result:

ok single line: '609656'

Test #8:

score: 0

Accepted

time: 15ms

memory: 70640kb

input:

output:

result:

ok single line: '64804'

Test #9:

score: 0

Accepted

time: 16ms

memory: 70496kb

input:

output:

result:

ok single line: '118638'

Test #10:

score: 0

Accepted

time: 15ms

memory: 70668kb

input:

output:

result:

ok single line: '22438'

Test #11:

score: 0

Accepted

time: 8ms

memory: 70492kb

input:

output:

result:

ok single line: '16796'

Test #12:

score: 0

Accepted

time: 7ms

memory: 70404kb

input:

output:

result:

ok single line: '82316'

Test #13:

score: 0

Accepted

time: 8ms

memory: 70444kb

input:

output:

result:

ok single line: '13700'

Test #14:

score: 0

Accepted

time: 16ms

memory: 70420kb

input:

output:

result:

ok single line: '3996'

Test #15:

score: 0

Accepted

time: 8ms

memory: 70424kb

input:

output:

result:

ok single line: '3490'

Test #16:

score: 0

Accepted

time: 12ms

memory: 70656kb

input:

output:

result:

ok single line: '1430'

Test #17:

score: 0

Accepted

time: 12ms

memory: 70504kb

input:

output:

result:

ok single line: '1430'

Test #18:

score: 0

Accepted

time: 16ms

memory: 70660kb

input:

output:

result:

ok single line: '3232'

Test #19:

score: 0

Accepted

time: 12ms

memory: 70452kb

input:

output:

result:

ok single line: '8970'

Test #20:

score: 0

Accepted

time: 1ms

memory: 70444kb

input:

output:

result:

ok single line: '3996'

Test #21:

score: 0

Accepted

time: 16ms

memory: 70516kb

input:

output:

result:

ok single line: '3332'

Test #22:

score: 0

Accepted

time: 1ms

memory: 70448kb

input:

output:

result:

ok single line: '1870'

Test #23:

score: 0

Accepted

time: 12ms

memory: 70440kb

input:

output:

result:

ok single line: '2416'

Test #24:

score: 0

Accepted

time: 12ms

memory: 70476kb

input:

output:

result:

ok single line: '2802'

Test #25:

score: 0

Accepted

time: 8ms

memory: 70472kb

input:

3
1 2
2 3

output:

result:

ok single line: '5'

Test #26:

score: 0

Accepted

time: 11ms

memory: 70508kb

input:

output:

result:

ok single line: '78904'

Subtask #2:

score: 10

Accepted

Test #27:

score: 10

Accepted

time: 175ms

memory: 138184kb

input:

output:

138172849

result:

ok single line: '138172849'

Test #28:

score: 0

Accepted

time: 19ms

memory: 89208kb

input:

output:

34585647

result:

ok single line: '34585647'

Test #29:

score: 0

Accepted

time: 102ms

memory: 116944kb

input:

output:

179814607

result:

ok single line: '179814607'

Test #30:

score: 0

Accepted

time: 17ms

memory: 75432kb

input:

output:

997745350

result:

ok single line: '997745350'

Test #31:

score: 0

Accepted

time: 22ms

memory: 77808kb

input:

output:

459486613

result:

ok single line: '459486613'

Test #32:

score: 0

Accepted

time: 171ms

memory: 137108kb

input:

output:

276300910

result:

ok single line: '276300910'

Test #33:

score: 0

Accepted

time: 48ms

memory: 96704kb

input:

output:

161112418

result:

ok single line: '161112418'

Test #34:

score: 0

Accepted

time: 68ms

memory: 98968kb

input:

output:

501208825

result:

ok single line: '501208825'

Test #35:

score: 0

Accepted

time: 30ms

memory: 87088kb

input:

output:

995483163

result:

ok single line: '995483163'

Test #36:

score: 0

Accepted

time: 77ms

memory: 102028kb

input:

output:

324344238

result:

ok single line: '324344238'

Subtask #3:

score: 10

Accepted

Dependency #1:

100%

Accepted

Test #37:

score: 10

Accepted

time: 16ms

memory: 70532kb

input:

output:

85351498

result:

ok single line: '85351498'

Test #38:

score: 0

Accepted

time: 4ms

memory: 70500kb

input:

output:

469047999

result:

ok single line: '469047999'

Test #39:

score: 0

Accepted

time: 15ms

memory: 70556kb

input:

output:

564120378

result:

ok single line: '564120378'

Test #40:

score: 0

Accepted

time: 20ms

memory: 70496kb

input:

output:

663766512

result:

ok single line: '663766512'

Test #41:

score: 0

Accepted

time: 19ms

memory: 70552kb

input:

output:

476848595

result:

ok single line: '476848595'

Test #42:

score: 0

Accepted

time: 11ms

memory: 70476kb

input:

output:

488457335

result:

ok single line: '488457335'

Test #43:

score: 0

Accepted

time: 12ms

memory: 70704kb

input:

output:

752198316

result:

ok single line: '752198316'

Test #44:

score: 0

Accepted

time: 4ms

memory: 70476kb

input:

output:

542252149

result:

ok single line: '542252149'

Test #45:

score: 0

Accepted

time: 7ms

memory: 70544kb

input:

output:

194863442

result:

ok single line: '194863442'

Test #46:

score: 0

Accepted

time: 16ms

memory: 70536kb

input:

output:

23651915

result:

ok single line: '23651915'

Test #47:

score: 0

Accepted

time: 16ms

memory: 70708kb

input:

output:

492545226

result:

ok single line: '492545226'

Test #48:

score: 0

Accepted

time: 24ms

memory: 70712kb

input:

output:

351974281

result:

ok single line: '351974281'

Test #49:

score: 0

Accepted

time: 8ms

memory: 70480kb

input:

output:

781206475

result:

ok single line: '781206475'

Test #50:

score: 0

Accepted

time: 8ms

memory: 70708kb

input:

output:

859563531

result:

ok single line: '859563531'

Test #51:

score: 0

Accepted

time: 3ms

memory: 70704kb

input:

output:

376484809

result:

ok single line: '376484809'

Test #52:

score: 0

Accepted

time: 9ms

memory: 70676kb

input:

output:

785968691

result:

ok single line: '785968691'

Test #53:

score: 0

Accepted

time: 1ms

memory: 70712kb

input:

output:

931047734

result:

ok single line: '931047734'

Test #54:

score: 0

Accepted

time: 15ms

memory: 70712kb

input:

output:

162400297

result:

ok single line: '162400297'

Test #55:

score: 0

Accepted

time: 8ms

memory: 70532kb

input:

output:

250839719

result:

ok single line: '250839719'

Test #56:

score: 0

Accepted

time: 8ms

memory: 70496kb

input:

output:

219471148

result:

ok single line: '219471148'

Test #57:

score: 0

Accepted

time: 12ms

memory: 70564kb

input:

output:

194863442

result:

ok single line: '194863442'

Test #58:

score: 0

Accepted

time: 12ms

memory: 70444kb

input:

output:

493588236

result:

ok single line: '493588236'

Test #59:

score: 0

Accepted

time: 8ms

memory: 70708kb

input:

output:

399365910

result:

ok single line: '399365910'

Test #60:

score: 0

Accepted

time: 8ms

memory: 70544kb

input:

output:

24503169

result:

ok single line: '24503169'

Subtask #4:

score: 25

Accepted

Dependency #3:

100%

Accepted

Test #61:

score: 25

Accepted

time: 8ms

memory: 70696kb

input:

output:

207339010

result:

ok single line: '207339010'

Test #62:

score: 0

Accepted

time: 12ms

memory: 70716kb

input:

output:

444163693

result:

ok single line: '444163693'

Test #63:

score: 0

Accepted

time: 12ms

memory: 70832kb

input:

output:

253999939

result:

ok single line: '253999939'

Test #64:

score: 0

Accepted

time: 12ms

memory: 70700kb

input:

output:

404981769

result:

ok single line: '404981769'

Test #65:

score: 0

Accepted

time: 21ms

memory: 70648kb

input:

output:

454043074

result:

ok single line: '454043074'

Test #66:

score: 0

Accepted

time: 8ms

memory: 70624kb

input:

output:

832905030

result:

ok single line: '832905030'

Test #67:

score: 0

Accepted

time: 8ms

memory: 70656kb

input:

output:

805899378

result:

ok single line: '805899378'

Test #68:

score: 0

Accepted

time: 12ms

memory: 70856kb

input:

output:

705490172

result:

ok single line: '705490172'

Test #69:

score: 0

Accepted

time: 11ms

memory: 70696kb

input:

output:

634401149

result:

ok single line: '634401149'

Test #70:

score: 0

Accepted

time: 8ms

memory: 70624kb

input:

output:

269904773

result:

ok single line: '269904773'

Test #71:

score: 0

Accepted

time: 16ms

memory: 70684kb

input:

output:

310957820

result:

ok single line: '310957820'

Test #72:

score: 0

Accepted

time: 4ms

memory: 70836kb

input:

output:

529454602

result:

ok single line: '529454602'

Test #73:

score: 0

Accepted

time: 13ms

memory: 70604kb

input:

output:

742352534

result:

ok single line: '742352534'

Test #74:

score: 0

Accepted

time: 4ms

memory: 70600kb

input:

output:

570704962

result:

ok single line: '570704962'

Test #75:

score: 0

Accepted

time: 15ms

memory: 70872kb

input:

output:

767444667

result:

ok single line: '767444667'

Test #76:

score: 0

Accepted

time: 12ms

memory: 70872kb

input:

output:

735270809

result:

ok single line: '735270809'

Test #77:

score: 0

Accepted

time: 12ms

memory: 70668kb

input:

output:

859967454

result:

ok single line: '859967454'

Test #78:

score: 0

Accepted

time: 3ms

memory: 70600kb

input:

output:

707392314

result:

ok single line: '707392314'

Test #79:

score: 0

Accepted

time: 7ms

memory: 70872kb

input:

output:

552215869

result:

ok single line: '552215869'

Test #80:

score: 0

Accepted

time: 4ms

memory: 70632kb

input:

output:

214555805

result:

ok single line: '214555805'

Test #81:

score: 0

Accepted

time: 11ms

memory: 70716kb

input:

output:

11910602

result:

ok single line: '11910602'

Test #82:

score: 0

Accepted

time: 7ms

memory: 70656kb

input:

output:

234907268

result:

ok single line: '234907268'

Test #83:

score: 0

Accepted

time: 11ms

memory: 70664kb

input:

output:

206263445

result:

ok single line: '206263445'

Test #84:

score: 0

Accepted

time: 7ms

memory: 70940kb

input:

output:

731555292

result:

ok single line: '731555292'

Subtask #5:

score: 20

Accepted

Dependency #4:

100%

Accepted

Test #85:

score: 20

Accepted

time: 13ms

memory: 72200kb

input:

output:

23954621

result:

ok single line: '23954621'

Test #86:

score: 0

Accepted

time: 7ms

memory: 72260kb

input:

output:

952035142

result:

ok single line: '952035142'

Test #87:

score: 0

Accepted

time: 7ms

memory: 72544kb

input:

output:

875356010

result:

ok single line: '875356010'

Test #88:

score: 0

Accepted

time: 7ms

memory: 72084kb

input:

output:

706621405

result:

ok single line: '706621405'

Test #89:

score: 0

Accepted

time: 10ms

memory: 71964kb

input:

output:

972656594

result:

ok single line: '972656594'

Test #90:

score: 0

Accepted

time: 14ms

memory: 72316kb

input:

output:

537838315

result:

ok single line: '537838315'

Test #91:

score: 0

Accepted

time: 8ms

memory: 72176kb

input:

output:

967361004

result:

ok single line: '967361004'

Test #92:

score: 0

Accepted

time: 15ms

memory: 72132kb

input:

output:

513218946

result:

ok single line: '513218946'

Test #93:

score: 0

Accepted

time: 15ms

memory: 72416kb

input:

output:

16995876

result:

ok single line: '16995876'

Test #94:

score: 0

Accepted

time: 4ms

memory: 72216kb

input:

output:

471041228

result:

ok single line: '471041228'

Test #95:

score: 0

Accepted

time: 11ms

memory: 72000kb

input:

output:

972656594

result:

ok single line: '972656594'

Test #96:

score: 0

Accepted

time: 8ms

memory: 72336kb

input:

output:

500366412

result:

ok single line: '500366412'

Test #97:

score: 0

Accepted

time: 15ms

memory: 72072kb

input:

output:

436627764

result:

ok single line: '436627764'

Test #98:

score: 0

Accepted

time: 12ms

memory: 72188kb

input:

output:

182295868

result:

ok single line: '182295868'

Test #99:

score: 0

Accepted

time: 18ms

memory: 72436kb

input:

output:

566795449

result:

ok single line: '566795449'

Test #100:

score: 0

Accepted

time: 11ms

memory: 72068kb

input:

output:

964271954

result:

ok single line: '964271954'

Test #101:

score: 0

Accepted

time: 26ms

memory: 72072kb

input:

output:

631187518

result:

ok single line: '631187518'

Test #102:

score: 0

Accepted

time: 3ms

memory: 72544kb

input:

output:

810088955

result:

ok single line: '810088955'

Test #103:

score: 0

Accepted

time: 25ms

memory: 72172kb

input:

output:

690741801

result:

ok single line: '690741801'

Test #104:

score: 0

Accepted

time: 13ms

memory: 72168kb

input:

output:

572499025

result:

ok single line: '572499025'

Test #105:

score: 0

Accepted

time: 11ms

memory: 72424kb

input:

output:

907316692

result:

ok single line: '907316692'

Test #106:

score: 0

Accepted

time: 11ms

memory: 72080kb

input:

output:

960051317

result:

ok single line: '960051317'

Test #107:

score: 0

Accepted

time: 11ms

memory: 72300kb

input:

output:

682235485

result:

ok single line: '682235485'

Test #108:

score: 0

Accepted

time: 7ms

memory: 72548kb

input:

output:

728680806

result:

ok single line: '728680806'

Subtask #6:

score: 30

Accepted

Dependency #5:

100%

Accepted

Test #109:

score: 30

Accepted

time: 185ms

memory: 106492kb

input:

output:

796804219

result:

ok single line: '796804219'

Test #110:

score: 0

Accepted

time: 271ms

memory: 114252kb

input:

output:

225232488

result:

ok single line: '225232488'

Test #111:

score: 0

Accepted

time: 202ms

memory: 137868kb

input:

output:

254007764

result:

ok single line: '254007764'

Test #112:

score: 0

Accepted

time: 167ms

memory: 90812kb

input:

output:

57313311

result:

ok single line: '57313311'

Test #113:

score: 0

Accepted

time: 191ms

memory: 90744kb

input:

output:

412800517

result:

ok single line: '412800517'

Test #114:

score: 0

Accepted

time: 198ms

memory: 125616kb

input:

output:

700780854

result:

ok single line: '700780854'

Test #115:

score: 0

Accepted

time: 204ms

memory: 106488kb

input:

output:

743222193

result:

ok single line: '743222193'

Test #116:

score: 0

Accepted

time: 266ms

memory: 114292kb

input:

output:

348028553

result:

ok single line: '348028553'

Test #117:

score: 0

Accepted

time: 186ms

memory: 137892kb

input:

output:

89020021

result:

ok single line: '89020021'

Test #118:

score: 0

Accepted

time: 184ms

memory: 90792kb

input:

output:

184832304

result:

ok single line: '184832304'

Test #119:

score: 0

Accepted

time: 204ms

memory: 91076kb

input:

output:

774236523

result:

ok single line: '774236523'

Test #120:

score: 0

Accepted

time: 202ms

memory: 125388kb

input:

output:

711005791

result:

ok single line: '711005791'

Test #121:

score: 0

Accepted

time: 227ms

memory: 106264kb

input:

output:

268262891

result:

ok single line: '268262891'

Test #122:

score: 0

Accepted

time: 245ms

memory: 114308kb

input:

output:

913953947

result:

ok single line: '913953947'

Test #123:

score: 0

Accepted

time: 185ms

memory: 138036kb

input:

output:

19609898

result:

ok single line: '19609898'

Test #124:

score: 0

Accepted

time: 192ms

memory: 90828kb

input:

output:

530310194

result:

ok single line: '530310194'

Test #125:

score: 0

Accepted

time: 206ms

memory: 90868kb

input:

output:

111211564

result:

ok single line: '111211564'

Test #126:

score: 0

Accepted

time: 241ms

memory: 125708kb

input:

output:

536050287

result:

ok single line: '536050287'

Test #127:

score: 0

Accepted

time: 204ms

memory: 106128kb

input:

output:

203664810

result:

ok single line: '203664810'

Test #128:

score: 0

Accepted

time: 268ms

memory: 114340kb

input:

output:

464943202

result:

ok single line: '464943202'

Test #129:

score: 0

Accepted

time: 177ms

memory: 138012kb

input:

output:

221495654

result:

ok single line: '221495654'

Test #130:

score: 0

Accepted

time: 207ms

memory: 91004kb

input:

output:

378087212

result:

ok single line: '378087212'

Test #131:

score: 0

Accepted

time: 219ms

memory: 90792kb

input:

output:

984482107

result:

ok single line: '984482107'

Test #132:

score: 0

Accepted

time: 214ms

memory: 125696kb

input:

output:

317476245

result:

ok single line: '317476245'