Submission #1817097
Source Code Expand
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <list>
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define FORSZ(i,a,v) FOR(i,a,SZ(v))
#define REPSZ(i,v) REP(i,SZ(v))
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
const int MAXN = 2000;
const int MOD = 1000000007;
const int INV2 = (MOD + 1) / 2;
int n;
int par[MAXN];
int fac[MAXN + 1];
int sz[MAXN];
int ways[MAXN][MAXN + 1][3]; // ways[i][j][k] = the number of ways to make directed paths in the subtree of i with total length j, with the root connected to k childs
void run() {
fac[0] = 1; FORE(i, 1, MAXN) fac[i] = (ll)fac[i - 1] * i%MOD;
scanf("%d", &n); par[0] = -1; FOR(i, 1, n) scanf("%d", &par[i]), --par[i];
REP(i, n) sz[i] = 1;
memset(ways, 0, sizeof(ways));
REP(i, n) ways[i][0][0] = 1;
for (int a = n - 1; a >= 0; --a) if(par[a]!=-1) {
int b = par[a];
for (int bk = 2; bk >= 0; --bk) for (int bj = sz[b] - 1; bj >= 0; --bj) if (ways[b][bj][bk] != 0) {
int bways = ways[b][bj][bk]; ways[b][bj][bk] = 0;
REPE(ak, 2) REPE(aj, sz[a] - 1) if (ways[a][aj][ak] != 0) REP(use, 2) {
if (use == 1 && (ak == 2 || bk == 2)) continue;
int aways = ways[a][aj][ak], nbk = bk + use, nbj = bj + aj + use, mlt = use == 0 ? 1 : ak == 1 && bk == 1 ? INV2 : ak == 1 || bk == 1 ? 1 : 2;
ways[b][nbj][nbk] = (ways[b][nbj][nbk] + (ll)bways*aways%MOD*mlt) % MOD;
}
}
sz[b] += sz[a];
//REPE(j, sz[b] - 1) REPE(k, 2) if (ways[b][j][k] != 0) printf("ways[%d][%d][%d]=%d\n", b + 1, j, k, ways[b][j][k]);
}
//REP(i, n) REPE(j, sz[i] - 1) REPE(k, 2) if (ways[i][j][k] != 0) printf("ways[%d][%d][%d]=%d\n", i + 1, j, k, ways[i][j][k]);
int ret = 0;
REPE(j, sz[0] - 1) REPE(k, 2) if (ways[0][j][k] != 0) {
int cur = (ll)ways[0][j][k] * fac[n - j] % MOD;
if (j % 2 == 1) cur = cur == 0 ? 0 : MOD - cur;
ret = (ret + cur) % MOD;
}
printf("%d\n", ret);
}
int main() {
run();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Awkward |
User |
krijgertje |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
2506 Byte |
Status |
AC |
Exec Time |
133 ms |
Memory |
47232 KB |
Compile Error
./Main.cpp: In function ‘void run()’:
./Main.cpp:48:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n); par[0] = -1; FOR(i, 1, n) scanf("%d", &par[i]), --par[i];
^
./Main.cpp:48:75: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n); par[0] = -1; FOR(i, 1, n) scanf("%d", &par[i]), --par[i];
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
a01, a02, a03, a04 |
All |
a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55 |
Case Name |
Status |
Exec Time |
Memory |
a01 |
AC |
17 ms |
47104 KB |
a02 |
AC |
17 ms |
47104 KB |
a03 |
AC |
17 ms |
47104 KB |
a04 |
AC |
17 ms |
47104 KB |
b05 |
AC |
18 ms |
47104 KB |
b06 |
AC |
33 ms |
47104 KB |
b07 |
AC |
57 ms |
47104 KB |
b08 |
AC |
62 ms |
47104 KB |
b09 |
AC |
51 ms |
47104 KB |
b10 |
AC |
41 ms |
47104 KB |
b11 |
AC |
25 ms |
47104 KB |
b12 |
AC |
20 ms |
47104 KB |
b13 |
AC |
20 ms |
47104 KB |
b14 |
AC |
25 ms |
47104 KB |
b15 |
AC |
62 ms |
47104 KB |
b16 |
AC |
20 ms |
47104 KB |
b17 |
AC |
18 ms |
47104 KB |
b18 |
AC |
18 ms |
47104 KB |
b19 |
AC |
61 ms |
47104 KB |
b20 |
AC |
50 ms |
47104 KB |
b21 |
AC |
41 ms |
47104 KB |
b22 |
AC |
62 ms |
47104 KB |
b23 |
AC |
55 ms |
47104 KB |
b24 |
AC |
39 ms |
47104 KB |
b25 |
AC |
32 ms |
47104 KB |
b26 |
AC |
33 ms |
47104 KB |
b27 |
AC |
34 ms |
47104 KB |
b28 |
AC |
31 ms |
47104 KB |
b29 |
AC |
52 ms |
47104 KB |
b30 |
AC |
52 ms |
47104 KB |
b31 |
AC |
51 ms |
47104 KB |
b32 |
AC |
55 ms |
47104 KB |
b33 |
AC |
77 ms |
47104 KB |
b34 |
AC |
133 ms |
47104 KB |
b35 |
AC |
107 ms |
47104 KB |
b36 |
AC |
77 ms |
47104 KB |
b37 |
AC |
76 ms |
47104 KB |
b38 |
AC |
76 ms |
47104 KB |
b39 |
AC |
84 ms |
47104 KB |
b40 |
AC |
80 ms |
47104 KB |
b41 |
AC |
68 ms |
47104 KB |
b42 |
AC |
79 ms |
47104 KB |
b43 |
AC |
76 ms |
47104 KB |
b44 |
AC |
76 ms |
47104 KB |
b45 |
AC |
58 ms |
47104 KB |
b46 |
AC |
57 ms |
47104 KB |
b47 |
AC |
56 ms |
47104 KB |
b48 |
AC |
56 ms |
47104 KB |
b49 |
AC |
57 ms |
47104 KB |
b50 |
AC |
35 ms |
47104 KB |
b51 |
AC |
33 ms |
47232 KB |
b52 |
AC |
33 ms |
47104 KB |
b53 |
AC |
32 ms |
47104 KB |
b54 |
AC |
32 ms |
47104 KB |
b55 |
AC |
68 ms |
47104 KB |