Submission #2554817
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) typedef vector<int> vi; typedef pair<int,int> pii; typedef long long ll; #define MOD 1000000007 int dp[252][252][252]; // dp[i][j][k] := len(i,j)->len(k) int n; vi children[252]; int par[252]; vi dfs(int p){ vi ret(1, 1); for(int c : children[p]){ vi V = dfs(c); vi nret(ret.size()+1 + V.size()+1,0); REP(i,ret.size())REP(j,V.size())REP(k,i+j+1){ (nret[k] += (ll)ret[i]*V[j]%MOD*dp[i][j][k]%MOD) %= MOD; } ret = nret; } vi nret(ret.size()+1,0); REP(i,ret.size())nret[i+1] = ret[i]; return nret; } int main(){ scanf("%d",&n); REP(i,n)par[i] = -1; REP(i,n-1){ int a,b; scanf("%d%d",&a,&b); children[a].push_back(b); par[b] = a; } int root = 0; REP(i,n)if(par[i]==-1)root=i; // dp dp[0][0][0] = 1; REP(i,202)REP(j,202)REP(k,202){ (dp[i+1][j][k+1] += dp[i][j][k]) %= MOD; (dp[i][j+1][k+1] += dp[i][j][k]) %= MOD; (dp[i+1][j+1][k+1] += dp[i][j][k]) %= MOD; } vi anses = dfs(root); int ans = 0; for(int x : anses){ ans = (ans+x)%MOD; } printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 順位付け |
User | rickytheta |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1219 Byte |
Status | RE |
Exec Time | 295 ms |
Memory | 51200 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:32:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:36:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&a,&b); ^
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample1.txt, 00-sample2.txt, 00-sample3.txt, 00-sample4.txt, 00-sample5.txt, random00.txt, random01.txt, random02.txt, random03.txt, random04.txt, random05.txt, random06.txt, random07.txt, random08.txt, random09.txt, random10.txt, random11.txt, random12.txt, random13.txt, random14.txt, random15.txt, random16.txt, random17.txt, random18.txt, random19.txt, random20.txt, random21.txt, random22.txt, random23.txt, random24.txt, random25.txt, random26.txt, random27.txt, random28.txt, random29.txt, random30.txt, random31.txt, random32.txt, random33.txt, random34.txt, random35.txt, random36.txt, random37.txt, random38.txt, random39.txt, random40.txt, random41.txt, random42.txt, random43.txt, random44.txt, random45.txt, random46.txt, random47.txt, random48.txt, random49.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample1.txt | AC | 49 ms | 51072 KB |
00-sample2.txt | AC | 49 ms | 51072 KB |
00-sample3.txt | AC | 49 ms | 51072 KB |
00-sample4.txt | AC | 49 ms | 51072 KB |
00-sample5.txt | AC | 52 ms | 51072 KB |
random00.txt | AC | 49 ms | 51072 KB |
random01.txt | AC | 49 ms | 51072 KB |
random02.txt | AC | 49 ms | 51072 KB |
random03.txt | AC | 49 ms | 51072 KB |
random04.txt | AC | 49 ms | 51072 KB |
random05.txt | AC | 49 ms | 51072 KB |
random06.txt | AC | 49 ms | 51072 KB |
random07.txt | AC | 49 ms | 51072 KB |
random08.txt | AC | 49 ms | 51072 KB |
random09.txt | AC | 49 ms | 51072 KB |
random10.txt | AC | 49 ms | 51072 KB |
random11.txt | AC | 49 ms | 51072 KB |
random12.txt | AC | 49 ms | 51072 KB |
random13.txt | AC | 49 ms | 51072 KB |
random14.txt | AC | 49 ms | 51072 KB |
random15.txt | AC | 49 ms | 51072 KB |
random16.txt | AC | 49 ms | 51072 KB |
random17.txt | AC | 49 ms | 51072 KB |
random18.txt | AC | 57 ms | 51200 KB |
random19.txt | AC | 49 ms | 51072 KB |
random20.txt | RE | 191 ms | 51072 KB |
random21.txt | RE | 162 ms | 51072 KB |
random22.txt | RE | 270 ms | 51072 KB |
random23.txt | RE | 172 ms | 51072 KB |
random24.txt | RE | 295 ms | 51072 KB |
random25.txt | RE | 181 ms | 51072 KB |
random26.txt | RE | 161 ms | 51072 KB |
random27.txt | RE | 191 ms | 51072 KB |
random28.txt | RE | 166 ms | 51072 KB |
random29.txt | RE | 169 ms | 51072 KB |
random30.txt | RE | 166 ms | 51072 KB |
random31.txt | RE | 184 ms | 51072 KB |
random32.txt | RE | 185 ms | 51072 KB |
random33.txt | RE | 159 ms | 51072 KB |
random34.txt | RE | 175 ms | 51072 KB |
random35.txt | RE | 169 ms | 51072 KB |
random36.txt | RE | 162 ms | 51072 KB |
random37.txt | RE | 175 ms | 51072 KB |
random38.txt | RE | 183 ms | 51072 KB |
random39.txt | RE | 168 ms | 51072 KB |
random40.txt | RE | 234 ms | 51072 KB |
random41.txt | RE | 163 ms | 51072 KB |
random42.txt | RE | 208 ms | 51072 KB |
random43.txt | RE | 191 ms | 51072 KB |
random44.txt | RE | 209 ms | 51072 KB |
random45.txt | RE | 164 ms | 51072 KB |
random46.txt | RE | 162 ms | 51072 KB |
random47.txt | RE | 184 ms | 51072 KB |
random48.txt | RE | 176 ms | 51072 KB |
random49.txt | RE | 209 ms | 51072 KB |