QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#95476	#5357. 芒果冰加了空气	chenshi	100 ✓	156ms	168424kb	C++	902b	2023-04-09 20:28:49	2023-04-09 20:28:51

Judging History

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

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

[2023-04-09 20:28:51]
评测

测评结果：100
用时：156ms
内存：168424kb

查看

[2023-04-09 20:28:49]
提交

answer

#include<cstdio>
using namespace std;
const int o=5010,MOD=1e9+7;
int n,h[o],cnt,C[o][o],f[o][o],g[o],s[o],ans;
struct Edge{int v,p;}e[o*2];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
void dfs(int nw,int fa){
	f[nw][s[nw]=1]=1;
	for(int i=h[nw];i;i=e[i].p) if(e[i].v^fa){
		dfs(e[i].v,nw);
		for(int j=s[e[i].v];j;--j) f[e[i].v][j-1]=(f[e[i].v][j-1]+f[e[i].v][j])%MOD;
		for(int j=1;j<=s[nw];++j) g[j]=f[nw][j],f[nw][j]=0;
		for(int j=1;j<=s[nw];++j) for(int k=0;k<=s[e[i].v];++k)
			f[nw][j+k]=(f[nw][j+k]+g[j]*1ll*f[e[i].v][k]%MOD*C[j-1+k][k])%MOD;
		s[nw]+=s[e[i].v];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=C[0][0]=1;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),ad(u,v),ad(v,u);
	dfs(1,0);
	for(int i=1;i<=n;++i) ans=(ans+f[1][i])%MOD;
	printf("%d",ans);
	return 0;
}

Source code, Language: C++

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

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 1ms

memory: 3616kb

input:

output:

result:

ok single line: '310862'

Test #2:

score: 0

Accepted

time: 0ms

memory: 7680kb

input:

output:

result:

ok single line: '64804'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

output:

result:

ok single line: '258182'

Test #4:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

output:

result:

ok single line: '16796'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3636kb

input:

output:

result:

ok single line: '78384'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

output:

result:

ok single line: '38896'

Test #7:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

output:

result:

ok single line: '609656'

Test #8:

score: 0

Accepted

time: 2ms

memory: 5732kb

input:

output:

result:

ok single line: '64804'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

result:

ok single line: '118638'

Test #10:

score: 0

Accepted

time: 0ms

memory: 5696kb

input:

output:

result:

ok single line: '22438'

Test #11:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

output:

result:

ok single line: '16796'

Test #12:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

output:

result:

ok single line: '82316'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

output:

result:

ok single line: '13700'

Test #14:

score: 0

Accepted

time: 1ms

memory: 3652kb

input:

output:

result:

ok single line: '3996'

Test #15:

score: 0

Accepted

time: 0ms

memory: 5728kb

input:

output:

result:

ok single line: '3490'

Test #16:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

output:

result:

ok single line: '1430'

Test #17:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

output:

result:

ok single line: '1430'

Test #18:

score: 0

Accepted

time: 1ms

memory: 3624kb

input:

output:

result:

ok single line: '3232'

Test #19:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

output:

result:

ok single line: '8970'

Test #20:

score: 0

Accepted

time: 0ms

memory: 5684kb

input:

output:

result:

ok single line: '3996'

Test #21:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

output:

result:

ok single line: '3332'

Test #22:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

output:

result:

ok single line: '1870'

Test #23:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

output:

result:

ok single line: '2416'

Test #24:

score: 0

Accepted

time: 2ms

memory: 3612kb

input:

output:

result:

ok single line: '2802'

Test #25:

score: 0

Accepted

time: 1ms

memory: 3612kb

input:

3
1 2
2 3

output:

result:

ok single line: '5'

Test #26:

score: 0

Accepted

time: 1ms

memory: 3664kb

input:

output:

result:

ok single line: '78904'

Subtask #2:

score: 10

Accepted

Test #27:

score: 10

Accepted

time: 156ms

memory: 168424kb

input:

output:

138172849

result:

ok single line: '138172849'

Test #28:

score: 0

Accepted

time: 20ms

memory: 90056kb

input:

output:

34585647

result:

ok single line: '34585647'

Test #29:

score: 0

Accepted

time: 84ms

memory: 126308kb

input:

output:

179814607

result:

ok single line: '179814607'

Test #30:

score: 0

Accepted

time: 0ms

memory: 37080kb

input:

output:

997745350

result:

ok single line: '997745350'

Test #31:

score: 0

Accepted

time: 3ms

memory: 49048kb

input:

output:

459486613

result:

ok single line: '459486613'

Test #32:

score: 0

Accepted

time: 153ms

memory: 166068kb

input:

output:

276300910

result:

ok single line: '276300910'

Test #33:

score: 0

Accepted

time: 46ms

memory: 92620kb

input:

output:

161112418

result:

ok single line: '161112418'

Test #34:

score: 0

Accepted

time: 47ms

memory: 95380kb

input:

output:

501208825

result:

ok single line: '501208825'

Test #35:

score: 0

Accepted

time: 16ms

memory: 82768kb

input:

output:

995483163

result:

ok single line: '995483163'

Test #36:

score: 0

Accepted

time: 55ms

memory: 101028kb

input:

output:

324344238

result:

ok single line: '324344238'

Subtask #3:

score: 10

Accepted

Dependency #1:

100%

Accepted

Test #37:

score: 10

Accepted

time: 2ms

memory: 7700kb

input:

output:

85351498

result:

ok single line: '85351498'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

469047999

result:

ok single line: '469047999'

Test #39:

score: 0

Accepted

time: 2ms

memory: 7692kb

input:

output:

564120378

result:

ok single line: '564120378'

Test #40:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

663766512

result:

ok single line: '663766512'

Test #41:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

output:

476848595

result:

ok single line: '476848595'

Test #42:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

488457335

result:

ok single line: '488457335'

Test #43:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

output:

752198316

result:

ok single line: '752198316'

Test #44:

score: 0

Accepted

time: 2ms

memory: 5764kb

input:

output:

542252149

result:

ok single line: '542252149'

Test #45:

score: 0

Accepted

time: 1ms

memory: 3704kb

input:

output:

194863442

result:

ok single line: '194863442'

Test #46:

score: 0

Accepted

time: 2ms

memory: 5720kb

input:

output:

23651915

result:

ok single line: '23651915'

Test #47:

score: 0

Accepted

time: 1ms

memory: 3664kb

input:

output:

492545226

result:

ok single line: '492545226'

Test #48:

score: 0

Accepted

time: 2ms

memory: 7688kb

input:

output:

351974281

result:

ok single line: '351974281'

Test #49:

score: 0

Accepted

time: 0ms

memory: 5720kb

input:

output:

781206475

result:

ok single line: '781206475'

Test #50:

score: 0

Accepted

time: 1ms

memory: 3696kb

input:

output:

859563531

result:

ok single line: '859563531'

Test #51:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

output:

376484809

result:

ok single line: '376484809'

Test #52:

score: 0

Accepted

time: 2ms

memory: 7688kb

input:

output:

785968691

result:

ok single line: '785968691'

Test #53:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

output:

931047734

result:

ok single line: '931047734'

Test #54:

score: 0

Accepted

time: 1ms

memory: 3700kb

input:

output:

162400297

result:

ok single line: '162400297'

Test #55:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

output:

250839719

result:

ok single line: '250839719'

Test #56:

score: 0

Accepted

time: 1ms

memory: 3728kb

input:

output:

219471148

result:

ok single line: '219471148'

Test #57:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

output:

194863442

result:

ok single line: '194863442'

Test #58:

score: 0

Accepted

time: 1ms

memory: 3700kb

input:

output:

493588236

result:

ok single line: '493588236'

Test #59:

score: 0

Accepted

time: 3ms

memory: 7676kb

input:

output:

399365910

result:

ok single line: '399365910'

Test #60:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

output:

24503169

result:

ok single line: '24503169'

Subtask #4:

score: 25

Accepted

Dependency #3:

100%

Accepted

Test #61:

score: 25

Accepted

time: 1ms

memory: 3836kb

input:

output:

207339010

result:

ok single line: '207339010'

Test #62:

score: 0

Accepted

time: 3ms

memory: 7752kb

input:

output:

444163693

result:

ok single line: '444163693'

Test #63:

score: 0

Accepted

time: 2ms

memory: 3820kb

input:

output:

253999939

result:

ok single line: '253999939'

Test #64:

score: 0

Accepted

time: 1ms

memory: 3812kb

input:

output:

404981769

result:

ok single line: '404981769'

Test #65:

score: 0

Accepted

time: 2ms

memory: 5832kb

input:

output:

454043074

result:

ok single line: '454043074'

Test #66:

score: 0

Accepted

time: 2ms

memory: 3824kb

input:

output:

832905030

result:

ok single line: '832905030'

Test #67:

score: 0

Accepted

time: 2ms

memory: 3852kb

input:

output:

805899378

result:

ok single line: '805899378'

Test #68:

score: 0

Accepted

time: 2ms

memory: 3796kb

input:

output:

705490172

result:

ok single line: '705490172'

Test #69:

score: 0

Accepted

time: 0ms

memory: 5872kb

input:

output:

634401149

result:

ok single line: '634401149'

Test #70:

score: 0

Accepted

time: 2ms

memory: 7880kb

input:

output:

269904773

result:

ok single line: '269904773'

Test #71:

score: 0

Accepted

time: 0ms

memory: 7712kb

input:

output:

310957820

result:

ok single line: '310957820'

Test #72:

score: 0

Accepted

time: 1ms

memory: 3824kb

input:

output:

529454602

result:

ok single line: '529454602'

Test #73:

score: 0

Accepted

time: 1ms

memory: 3816kb

input:

output:

742352534

result:

ok single line: '742352534'

Test #74:

score: 0

Accepted

time: 1ms

memory: 3860kb

input:

output:

570704962

result:

ok single line: '570704962'

Test #75:

score: 0

Accepted

time: 1ms

memory: 3844kb

input:

output:

767444667

result:

ok single line: '767444667'

Test #76:

score: 0

Accepted

time: 2ms

memory: 7860kb

input:

output:

735270809

result:

ok single line: '735270809'

Test #77:

score: 0

Accepted

time: 3ms

memory: 7804kb

input:

output:

859967454

result:

ok single line: '859967454'

Test #78:

score: 0

Accepted

time: 0ms

memory: 3884kb

input:

output:

707392314

result:

ok single line: '707392314'

Test #79:

score: 0

Accepted

time: 2ms

memory: 5884kb

input:

output:

552215869

result:

ok single line: '552215869'

Test #80:

score: 0

Accepted

time: 1ms

memory: 3836kb

input:

output:

214555805

result:

ok single line: '214555805'

Test #81:

score: 0

Accepted

time: 0ms

memory: 7840kb

input:

output:

11910602

result:

ok single line: '11910602'

Test #82:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

output:

234907268

result:

ok single line: '234907268'

Test #83:

score: 0

Accepted

time: 2ms

memory: 5872kb

input:

output:

206263445

result:

ok single line: '206263445'

Test #84:

score: 0

Accepted

time: 2ms

memory: 5872kb

input:

output:

731555292

result:

ok single line: '731555292'

Subtask #5:

score: 20

Accepted

Dependency #4:

100%

Accepted

Test #85:

score: 20

Accepted

time: 0ms

memory: 20016kb

input:

output:

23954621

result:

ok single line: '23954621'

Test #86:

score: 0

Accepted

time: 0ms

memory: 20372kb

input:

output:

952035142

result:

ok single line: '952035142'

Test #87:

score: 0

Accepted

time: 1ms

memory: 20052kb

input:

output:

875356010

result:

ok single line: '875356010'

Test #88:

score: 0

Accepted

time: 2ms

memory: 20212kb

input:

output:

706621405

result:

ok single line: '706621405'

Test #89:

score: 0

Accepted

time: 3ms

memory: 19988kb

input:

output:

972656594

result:

ok single line: '972656594'

Test #90:

score: 0

Accepted

time: 3ms

memory: 20324kb

input:

output:

537838315

result:

ok single line: '537838315'

Test #91:

score: 0

Accepted

time: 1ms

memory: 20148kb

input:

output:

967361004

result:

ok single line: '967361004'

Test #92:

score: 0

Accepted

time: 4ms

memory: 20280kb

input:

output:

513218946

result:

ok single line: '513218946'

Test #93:

score: 0

Accepted

time: 0ms

memory: 20076kb

input:

output:

16995876

result:

ok single line: '16995876'

Test #94:

score: 0

Accepted

time: 1ms

memory: 18232kb

input:

output:

471041228

result:

ok single line: '471041228'

Test #95:

score: 0

Accepted

time: 1ms

memory: 19988kb

input:

output:

972656594

result:

ok single line: '972656594'

Test #96:

score: 0

Accepted

time: 1ms

memory: 20024kb

input:

output:

500366412

result:

ok single line: '500366412'

Test #97:

score: 0

Accepted

time: 1ms

memory: 18372kb

input:

output:

436627764

result:

ok single line: '436627764'

Test #98:

score: 0

Accepted

time: 1ms

memory: 20320kb

input:

output:

182295868

result:

ok single line: '182295868'

Test #99:

score: 0

Accepted

time: 0ms

memory: 20240kb

input:

output:

566795449

result:

ok single line: '566795449'

Test #100:

score: 0

Accepted

time: 1ms

memory: 20144kb

input:

output:

964271954

result:

ok single line: '964271954'

Test #101:

score: 0

Accepted

time: 1ms

memory: 18316kb

input:

output:

631187518

result:

ok single line: '631187518'

Test #102:

score: 0

Accepted

time: 0ms

memory: 18408kb

input:

output:

810088955

result:

ok single line: '810088955'

Test #103:

score: 0

Accepted

time: 0ms

memory: 20168kb

input:

output:

690741801

result:

ok single line: '690741801'

Test #104:

score: 0

Accepted

time: 0ms

memory: 18364kb

input:

output:

572499025

result:

ok single line: '572499025'

Test #105:

score: 0

Accepted

time: 1ms

memory: 20120kb

input:

output:

907316692

result:

ok single line: '907316692'

Test #106:

score: 0

Accepted

time: 1ms

memory: 20072kb

input:

output:

960051317

result:

ok single line: '960051317'

Test #107:

score: 0

Accepted

time: 1ms

memory: 20100kb

input:

output:

682235485

result:

ok single line: '682235485'

Test #108:

score: 0

Accepted

time: 1ms

memory: 20368kb

input:

output:

728680806

result:

ok single line: '728680806'

Subtask #6:

score: 30

Accepted

Dependency #5:

100%

Accepted

Test #109:

score: 30

Accepted

time: 105ms

memory: 135968kb

input:

output:

796804219

result:

ok single line: '796804219'

Test #110:

score: 0

Accepted

time: 92ms

memory: 143632kb

input:

output:

225232488

result:

ok single line: '225232488'

Test #111:

score: 0

Accepted

time: 144ms

memory: 167520kb

input:

output:

254007764

result:

ok single line: '254007764'

Test #112:

score: 0

Accepted

time: 112ms

memory: 120428kb

input:

output:

57313311

result:

ok single line: '57313311'

Test #113:

score: 0

Accepted

time: 116ms

memory: 121284kb

input:

output:

412800517

result:

ok single line: '412800517'

Test #114:

score: 0

Accepted

time: 128ms

memory: 155588kb

input:

output:

700780854

result:

ok single line: '700780854'

Test #115:

score: 0

Accepted

time: 102ms

memory: 136500kb

input:

output:

743222193

result:

ok single line: '743222193'

Test #116:

score: 0

Accepted

time: 104ms

memory: 143168kb

input:

output:

348028553

result:

ok single line: '348028553'

Test #117:

score: 0

Accepted

time: 143ms

memory: 167992kb

input:

output:

89020021

result:

ok single line: '89020021'

Test #118:

score: 0

Accepted

time: 129ms

memory: 120052kb

input:

output:

184832304

result:

ok single line: '184832304'

Test #119:

score: 0

Accepted

time: 122ms

memory: 120048kb

input:

output:

774236523

result:

ok single line: '774236523'

Test #120:

score: 0

Accepted

time: 143ms

memory: 154652kb

input:

output:

711005791

result:

ok single line: '711005791'

Test #121:

score: 0

Accepted

time: 126ms

memory: 136388kb

input:

output:

268262891

result:

ok single line: '268262891'

Test #122:

score: 0

Accepted

time: 111ms

memory: 144176kb

input:

output:

913953947

result:

ok single line: '913953947'

Test #123:

score: 0

Accepted

time: 156ms

memory: 168108kb

input:

output:

19609898

result:

ok single line: '19609898'

Test #124:

score: 0

Accepted

time: 115ms

memory: 121016kb

input:

output:

530310194

result:

ok single line: '530310194'

Test #125:

score: 0

Accepted

time: 118ms

memory: 121260kb

input:

output:

111211564

result:

ok single line: '111211564'

Test #126:

score: 0

Accepted

time: 133ms

memory: 154736kb

input:

output:

536050287

result:

ok single line: '536050287'

Test #127:

score: 0

Accepted

time: 95ms

memory: 135492kb

input:

output:

203664810

result:

ok single line: '203664810'

Test #128:

score: 0

Accepted

time: 98ms

memory: 143764kb

input:

output:

464943202

result:

ok single line: '464943202'

Test #129:

score: 0

Accepted

time: 149ms

memory: 167216kb

input:

output:

221495654

result:

ok single line: '221495654'

Test #130:

score: 0

Accepted

time: 101ms

memory: 120916kb

input:

output:

378087212

result:

ok single line: '378087212'

Test #131:

score: 0

Accepted

time: 122ms

memory: 120252kb

input:

output:

984482107

result:

ok single line: '984482107'

Test #132:

score: 0

Accepted

time: 143ms

memory: 154436kb

input:

output:

317476245

result:

ok single line: '317476245'