QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489857 | #5367. 递增树列 | hos_lyric | 100 ✓ | 16ms | 4328kb | C++14 | 7.8kb | 2024-07-25 05:09:06 | 2024-07-25 05:09:07 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 1000000007;
using Mint = ModInt<MO>;
constexpr int LIM_INV = 1010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];
void prepare() {
inv[1] = 1;
for (int i = 2; i < LIM_INV; ++i) {
inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
}
fac[0] = invFac[0] = 1;
for (int i = 1; i < LIM_INV; ++i) {
fac[i] = fac[i - 1] * i;
invFac[i] = invFac[i - 1] * inv[i];
}
}
Mint binom(Int n, Int k) {
if (n < 0) {
if (k >= 0) {
return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
} else if (n - k >= 0) {
return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
} else {
return 0;
}
} else {
if (0 <= k && k <= n) {
assert(n < LIM_INV);
return fac[n] * invFac[k] * invFac[n - k];
} else {
return 0;
}
}
}
/*
lca must go into subtree
u[D]: last lca
u[0], ..., u[D]: path from root
T[d][j] (0 <= d <= D): subtrees
for d = D, ..., 0
insert u[d] and T[d][j]
put some at the end (lca = u[d] part)
no adj. from the same subtree
remaining: regard as new subtree
if lca = u[d] part is >= 1, rightmost must not be from this new subtree
*/
int N;
vector<int> A, B;
vector<vector<int>> graph;
vector<int> sz;
// u, # remaining
Mint dp[110][110];
// # chosen, # pie block
Mint crt[2][110][110], nxt[2][110][110];
Mint f[110][110], g[110][110];
void dfs(int u, int p) {
for (const int v : graph[u]) if (p != v) {
dfs(v, u);
}
sz[u] = 1;
for (int h = 0; h < 2; ++h) for (int k = 0; k <= sz[u]; ++k) fill(crt[h][k], crt[h][k] + (sz[u] - k + 1), 0);
crt[0][0][1] = crt[0][1][0] = 1;
for (const int v : graph[u]) if (p != v) {
// use some of them and line up -> cut into PIE blocks
for (int k = 0; k <= sz[v]; ++k) fill(f[k], f[k] + (sz[v] - k + 1), 0);
for (int k = 0; k <= sz[v]; ++k) fill(g[k], g[k] + (sz[v] - k + 1), 0);
for (int k = 0; k <= sz[v]; ++k) for (int a = 0; a <= sz[v] - k; ++a) f[k][a] += (fac[sz[v]] * invFac[k]) * binom((sz[v] - k) - 1, a - 1) * ((sz[v]-k-a)&1?-1:+1) * invFac[a];
for (int k = 0; k <= sz[v]; ++k) for (int l = 0; l <= k; ++l) for (int a = 0; a <= k - l; ++a) g[l][a] += dp[v][k] * (fac[k] * invFac[l]) * binom((k - l) - 1, a - 1) * ((k-l-a)&1?-1:+1) * invFac[a];
// conv
for (int h = 0; h < 2; ++h) for (int k = 0; k <= sz[u] + sz[v]; ++k) fill(nxt[h][k], nxt[h][k] + (sz[u] + sz[v] - k + 1), 0);
for (int ku = 0; ku <= sz[u]; ++ku) for (int kv = 0; kv <= sz[v]; ++kv) {
for (int au = 0; au <= sz[u] - ku; ++au) for (int av = 0; av <= sz[v] - kv; ++av) {
nxt[0][ku + kv][au + av] += crt[0][ku][au] * f[kv][av];
nxt[1][ku + kv][au + av] += crt[1][ku][au] * f[kv][av];
nxt[1][ku + kv][au + av] += crt[0][ku][au] * g[kv][av];
// ban rightmost
if (av) nxt[1][ku + kv][au + av - 1] -= crt[0][ku][au] * g[kv][av] * av;
}
}
for (int h = 0; h < 2; ++h) for (int k = 0; k <= sz[u] + sz[v]; ++k) copy(nxt[h][k], nxt[h][k] + (sz[u] + sz[v] - k + 1), crt[h][k]);
sz[u] += sz[v];
}
// start
for (int k = 0; k <= sz[u] - 2; ++k) for (int a = 0; a <= sz[u] - k; ++a) if (crt[0][k][a]) {
// cerr<<__LINE__<<": "<<u<<"; "<<k<<" "<<a<<": "<<crt[0][k][a]<<" "<<fac[a]<<endl;
dp[u][k] += crt[0][k][a] * fac[a];
}
// continue
for (int k = 0; k <= sz[u]; ++k) for (int a = 0; a <= sz[u] - k; ++a) if (crt[1][k][a]) {
// cerr<<__LINE__<<": "<<u<<"; "<<k<<" "<<a<<": "<<crt[1][k][a]<<" "<<fac[a]<<endl;
dp[u][k] += crt[1][k][a] * fac[a];
}
// cerr<<"dp["<<u<<"] = ";pv(dp[u],dp[u]+(sz[u]+1));
}
int main() {
prepare();
for (; ~scanf("%d", &N); ) {
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
graph.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
sz.assign(N, 0);
memset(dp, 0, sizeof(dp));
dfs(0, -1);
printf("%u\n", dp[0][0].x);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 1ms
memory: 3892kb
input:
7 1 2 2 3 2 4 1 5 5 6 3 7
output:
712
result:
ok single line: '712'
Test #2:
score: 9
Accepted
time: 0ms
memory: 4156kb
input:
5 1 2 1 3 3 4 4 5
output:
44
result:
ok single line: '44'
Test #3:
score: 9
Accepted
time: 0ms
memory: 3864kb
input:
7 1 2 2 3 1 4 3 5 3 6 2 7
output:
576
result:
ok single line: '576'
Test #4:
score: 9
Accepted
time: 0ms
memory: 3868kb
input:
8 1 2 1 3 3 4 2 5 2 6 1 7 2 8
output:
6912
result:
ok single line: '6912'
Test #5:
score: 9
Accepted
time: 0ms
memory: 3828kb
input:
8 1 2 2 3 2 4 1 5 2 6 3 7 5 8
output:
3360
result:
ok single line: '3360'
Subtask #2:
score: 11
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 11
Accepted
time: 0ms
memory: 3956kb
input:
14 1 2 1 3 1 4 1 5 1 6 4 7 2 8 1 9 4 10 7 11 9 12 2 13 11 14
output:
389151297
result:
ok single line: '389151297'
Test #7:
score: 11
Accepted
time: 0ms
memory: 4172kb
input:
13 1 2 2 3 2 4 2 5 4 6 4 7 3 8 4 9 6 10 4 11 11 12 6 13
output:
17381952
result:
ok single line: '17381952'
Test #8:
score: 11
Accepted
time: 0ms
memory: 3900kb
input:
12 1 2 2 3 2 4 1 5 5 6 4 7 7 8 5 9 4 10 1 11 7 12
output:
4993920
result:
ok single line: '4993920'
Test #9:
score: 11
Accepted
time: 1ms
memory: 3988kb
input:
15 1 2 1 3 2 4 4 5 2 6 6 7 2 8 8 9 2 10 4 11 8 12 4 13 5 14 9 15
output:
818474475
result:
ok single line: '818474475'
Test #10:
score: 11
Accepted
time: 0ms
memory: 4168kb
input:
15 1 2 1 3 2 4 3 5 2 6 5 7 4 8 4 9 1 10 10 11 8 12 10 13 13 14 7 15
output:
16041048
result:
ok single line: '16041048'
Subtask #3:
score: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 15
Accepted
time: 1ms
memory: 3908kb
input:
25 1 2 1 3 3 4 4 5 2 6 2 7 5 8 5 9 1 10 10 11 9 12 5 13 4 14 12 15 1 16 14 17 2 18 2 19 16 20 18 21 18 22 20 23 17 24 19 25
output:
179142361
result:
ok single line: '179142361'
Test #12:
score: 15
Accepted
time: 0ms
memory: 3996kb
input:
24 1 2 1 3 2 4 1 5 2 6 2 7 6 8 1 9 1 10 1 11 8 12 6 13 13 14 12 15 2 16 5 17 12 18 8 19 11 20 17 21 21 22 19 23 18 24
output:
680835791
result:
ok single line: '680835791'
Test #13:
score: 15
Accepted
time: 1ms
memory: 3860kb
input:
23 1 2 1 3 3 4 2 5 2 6 5 7 4 8 7 9 4 10 8 11 2 12 8 13 1 14 14 15 9 16 7 17 9 18 5 19 16 20 15 21 10 22 17 23
output:
613299173
result:
ok single line: '613299173'
Test #14:
score: 15
Accepted
time: 1ms
memory: 3904kb
input:
24 1 2 1 3 1 4 1 5 2 6 3 7 1 8 6 9 6 10 10 11 6 12 10 13 6 14 4 15 5 16 1 17 8 18 1 19 17 20 2 21 19 22 20 23 15 24
output:
990332459
result:
ok single line: '990332459'
Test #15:
score: 15
Accepted
time: 1ms
memory: 3904kb
input:
27 1 2 1 3 2 4 1 5 3 6 1 7 4 8 5 9 5 10 9 11 10 12 11 13 6 14 3 15 6 16 5 17 4 18 14 19 3 20 13 21 1 22 8 23 6 24 4 25 12 26 25 27
output:
254905851
result:
ok single line: '254905851'
Test #16:
score: 15
Accepted
time: 1ms
memory: 3916kb
input:
28 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
output:
245512165
result:
ok single line: '245512165'
Test #17:
score: 15
Accepted
time: 1ms
memory: 3912kb
input:
25 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25
output:
440732388
result:
ok single line: '440732388'
Test #18:
score: 15
Accepted
time: 1ms
memory: 3872kb
input:
25 1 2 2 3 2 4 3 5 3 6 4 7 6 8 8 9 8 10 9 11 9 12 11 13 11 14 12 15 14 16 15 17 16 18 16 19 19 20 19 21 20 22 21 23 21 24 24 25
output:
222462817
result:
ok single line: '222462817'
Test #19:
score: 15
Accepted
time: 1ms
memory: 3940kb
input:
30 1 2 1 3 1 4 2 5 5 6 3 7 7 8 5 9 6 10 7 11 10 12 9 13 11 14 11 15 14 16 13 17 16 18 15 19 19 20 20 21 18 22 22 23 21 24 24 25 22 26 24 27 25 28 27 29 27 30
output:
915280502
result:
ok single line: '915280502'
Test #20:
score: 15
Accepted
time: 1ms
memory: 4208kb
input:
29 1 2 2 3 1 4 4 5 2 6 5 7 3 8 7 9 5 10 7 11 10 12 9 13 13 14 11 15 11 16 12 17 17 18 17 19 17 20 16 21 17 22 20 23 22 24 23 25 22 26 25 27 24 28 28 29
output:
847984210
result:
ok single line: '847984210'
Test #21:
score: 15
Accepted
time: 1ms
memory: 3956kb
input:
30 1 2 1 3 3 4 4 5 4 6 5 7 6 8 6 9 8 10 6 11 11 12 10 13 9 14 9 15 15 16 15 17 17 18 16 19 16 20 19 21 16 22 20 23 20 24 21 25 20 26 22 27 25 28 26 29 28 30
output:
203499669
result:
ok single line: '203499669'
Test #22:
score: 15
Accepted
time: 1ms
memory: 3888kb
input:
29 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 7 18 1 19 6 20 16 21 18 22 19 23 15 24 6 25 3 26 16 27 9 28 21 29
output:
673029660
result:
ok single line: '673029660'
Test #23:
score: 15
Accepted
time: 1ms
memory: 3896kb
input:
25 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 2 20 10 21 2 22 14 23 9 24 5 25
output:
463358446
result:
ok single line: '463358446'
Test #24:
score: 15
Accepted
time: 1ms
memory: 3908kb
input:
30 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 16 20 14 21 8 22 13 23 3 24 16 25 13 26 18 27 10 28 5 29 21 30
output:
2581770
result:
ok single line: '2581770'
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #25:
score: 25
Accepted
time: 1ms
memory: 4220kb
input:
42 1 2 1 3 2 4 1 5 1 6 1 7 6 8 2 9 5 10 2 11 2 12 7 13 9 14 3 15 4 16 3 17 8 18 11 19 10 20 12 21 16 22 6 23 13 24 19 25 8 26 22 27 19 28 7 29 1 30 2 31 30 32 27 33 28 34 18 35 6 36 24 37 21 38 11 39 22 40 22 41 3 42
output:
475818143
result:
ok single line: '475818143'
Test #26:
score: 25
Accepted
time: 1ms
memory: 3996kb
input:
47 1 2 2 3 2 4 2 5 4 6 3 7 6 8 4 9 7 10 6 11 3 12 8 13 4 14 3 15 9 16 12 17 1 18 4 19 7 20 1 21 4 22 3 23 12 24 5 25 7 26 18 27 23 28 21 29 4 30 6 31 11 32 27 33 25 34 28 35 13 36 9 37 21 38 31 39 13 40 20 41 34 42 12 43 36 44 13 45 25 46 42 47
output:
574349748
result:
ok single line: '574349748'
Test #27:
score: 25
Accepted
time: 1ms
memory: 4220kb
input:
47 1 2 2 3 3 4 4 5 5 6 2 7 7 8 6 9 7 10 7 11 4 12 11 13 7 14 6 15 10 16 16 17 7 18 17 19 3 20 15 21 21 22 11 23 10 24 13 25 10 26 6 27 21 28 4 29 2 30 6 31 16 32 29 33 4 34 20 35 34 36 19 37 3 38 21 39 29 40 8 41 31 42 37 43 38 44 23 45 43 46 28 47
output:
284808122
result:
ok single line: '284808122'
Test #28:
score: 25
Accepted
time: 1ms
memory: 3964kb
input:
48 1 2 2 3 1 4 1 5 3 6 1 7 7 8 6 9 8 10 8 11 3 12 11 13 6 14 13 15 4 16 4 17 9 18 17 19 11 20 11 21 3 22 2 23 8 24 23 25 7 26 4 27 21 28 11 29 4 30 21 31 20 32 14 33 20 34 21 35 26 36 10 37 8 38 2 39 27 40 9 41 14 42 28 43 31 44 2 45 10 46 25 47 43 48
output:
728582173
result:
ok single line: '728582173'
Test #29:
score: 25
Accepted
time: 1ms
memory: 4228kb
input:
46 1 2 1 3 1 4 3 5 3 6 1 7 5 8 6 9 3 10 1 11 6 12 8 13 3 14 7 15 2 16 11 17 17 18 18 19 4 20 5 21 7 22 18 23 10 24 20 25 16 26 22 27 17 28 17 29 17 30 25 31 1 32 7 33 2 34 12 35 27 36 31 37 13 38 34 39 30 40 5 41 34 42 31 43 2 44 8 45 43 46
output:
830913254
result:
ok single line: '830913254'
Test #30:
score: 25
Accepted
time: 2ms
memory: 4256kb
input:
42 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
output:
118430285
result:
ok single line: '118430285'
Test #31:
score: 25
Accepted
time: 1ms
memory: 3884kb
input:
44 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44
output:
10503098
result:
ok single line: '10503098'
Test #32:
score: 25
Accepted
time: 2ms
memory: 3968kb
input:
48 1 2 2 3 1 4 2 5 5 6 5 7 6 8 7 9 7 10 8 11 11 12 10 13 12 14 14 15 15 16 15 17 17 18 17 19 18 20 18 21 19 22 20 23 23 24 22 25 24 26 26 27 27 28 27 29 28 30 29 31 31 32 32 33 33 34 33 35 34 36 34 37 36 38 36 39 38 40 40 41 40 42 40 43 42 44 44 45 45 46 44 47 46 48
output:
236779386
result:
ok single line: '236779386'
Test #33:
score: 25
Accepted
time: 1ms
memory: 4216kb
input:
43 1 2 1 3 3 4 4 5 4 6 4 7 4 8 8 9 7 10 7 11 10 12 9 13 12 14 12 15 14 16 15 17 17 18 17 19 18 20 19 21 19 22 20 23 21 24 22 25 23 26 24 27 27 28 25 29 26 30 30 31 29 32 32 33 31 34 33 35 33 36 33 37 37 38 35 39 37 40 37 41 38 42 42 43
output:
472278844
result:
ok single line: '472278844'
Test #34:
score: 25
Accepted
time: 2ms
memory: 4252kb
input:
49 1 2 2 3 2 4 4 5 1 6 3 7 7 8 6 9 7 10 10 11 7 12 10 13 9 14 11 15 14 16 15 17 15 18 14 19 18 20 19 21 17 22 22 23 20 24 24 25 24 26 23 27 25 28 25 29 27 30 29 31 27 32 29 33 31 34 34 35 31 36 34 37 35 38 35 39 37 40 36 41 40 42 39 43 42 44 42 45 42 46 45 47 46 48 45 49
output:
918870657
result:
ok single line: '918870657'
Test #35:
score: 25
Accepted
time: 1ms
memory: 3996kb
input:
46 1 2 1 3 2 4 3 5 3 6 6 7 4 8 8 9 9 10 8 11 8 12 12 13 9 14 12 15 14 16 12 17 13 18 18 19 19 20 15 21 21 22 20 23 18 24 20 25 23 26 23 27 26 28 24 29 24 30 29 31 28 32 31 33 31 34 31 35 33 36 36 37 32 38 34 39 35 40 39 41 38 42 37 43 41 44 43 45 45 46
output:
85610243
result:
ok single line: '85610243'
Test #36:
score: 25
Accepted
time: 1ms
memory: 3968kb
input:
48 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 2 23 1 24 23 25 18 26 10 27 1 28 15 29 7 30 6 31 26 32 17 33 30 34 10 35 35 36 10 37 29 38 31 39 35 40 18 41 34 42 3 43 30 44 34 45 45 46 43 47 27 48
output:
773530270
result:
ok single line: '773530270'
Test #37:
score: 25
Accepted
time: 0ms
memory: 3932kb
input:
45 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 12 24 11 25 2 26 13 27 7 28 4 29 5 30 29 31 4 32 9 33 32 34 21 35 12 36 20 37 3 38 20 39 35 40 36 41 23 42 31 43 5 44 31 45
output:
600462689
result:
ok single line: '600462689'
Test #38:
score: 25
Accepted
time: 1ms
memory: 4192kb
input:
45 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 24 25 24 26 26 27 16 28 4 29 23 30 16 31 23 32 6 33 27 34 25 35 12 36 4 37 31 38 4 39 8 40 18 41 27 42 35 43 22 44 23 45
output:
563685126
result:
ok single line: '563685126'
Subtask #5:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #39:
score: 40
Accepted
time: 3ms
memory: 4308kb
input:
73 1 2 1 3 2 4 3 5 5 6 3 7 3 8 2 9 3 10 3 11 8 12 3 13 9 14 12 15 11 16 3 17 11 18 18 19 3 20 5 21 1 22 2 23 23 24 7 25 15 26 17 27 22 28 28 29 13 30 24 31 22 32 15 33 25 34 4 35 5 36 28 37 8 38 6 39 12 40 6 41 4 42 30 43 26 44 11 45 8 46 35 47 36 48 45 49 8 50 7 51 43 52 27 53 49 54 53 55 52 56 8 5...
output:
518761011
result:
ok single line: '518761011'
Test #40:
score: 40
Accepted
time: 2ms
memory: 4100kb
input:
80 1 2 1 3 2 4 3 5 1 6 6 7 7 8 5 9 2 10 7 11 4 12 3 13 9 14 12 15 13 16 5 17 10 18 4 19 1 20 14 21 16 22 13 23 17 24 8 25 11 26 23 27 5 28 27 29 23 30 8 31 11 32 21 33 3 34 25 35 6 36 24 37 12 38 6 39 37 40 10 41 2 42 27 43 23 44 28 45 20 46 46 47 15 48 45 49 40 50 36 51 13 52 49 53 52 54 36 55 19 5...
output:
908706975
result:
ok single line: '908706975'
Test #41:
score: 40
Accepted
time: 3ms
memory: 4300kb
input:
77 1 2 2 3 1 4 2 5 1 6 1 7 3 8 2 9 6 10 7 11 8 12 4 13 12 14 14 15 4 16 10 17 7 18 7 19 9 20 14 21 10 22 9 23 23 24 5 25 22 26 16 27 21 28 10 29 1 30 26 31 5 32 12 33 31 34 3 35 22 36 30 37 17 38 20 39 20 40 14 41 33 42 5 43 1 44 36 45 30 46 27 47 43 48 13 49 29 50 5 51 10 52 47 53 20 54 24 55 3 56 ...
output:
471949293
result:
ok single line: '471949293'
Test #42:
score: 40
Accepted
time: 3ms
memory: 3996kb
input:
80 1 2 2 3 2 4 4 5 4 6 5 7 2 8 1 9 7 10 6 11 10 12 2 13 8 14 14 15 3 16 9 17 1 18 10 19 10 20 5 21 9 22 9 23 23 24 13 25 8 26 18 27 27 28 4 29 10 30 3 31 1 32 16 33 32 34 21 35 19 36 17 37 13 38 38 39 38 40 8 41 33 42 4 43 12 44 15 45 19 46 19 47 4 48 47 49 6 50 24 51 29 52 12 53 48 54 31 55 15 56 5...
output:
112450382
result:
ok single line: '112450382'
Test #43:
score: 40
Accepted
time: 3ms
memory: 4020kb
input:
76 1 2 2 3 3 4 1 5 2 6 6 7 2 8 2 9 1 10 6 11 4 12 5 13 7 14 10 15 14 16 16 17 16 18 14 19 10 20 5 21 13 22 2 23 5 24 19 25 14 26 13 27 7 28 15 29 1 30 20 31 1 32 13 33 9 34 30 35 34 36 28 37 2 38 35 39 12 40 29 41 21 42 40 43 6 44 18 45 2 46 35 47 38 48 15 49 25 50 23 51 38 52 23 53 17 54 4 55 40 56...
output:
815118641
result:
ok single line: '815118641'
Test #44:
score: 40
Accepted
time: 16ms
memory: 4080kb
input:
74 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 51 52 52 53 53...
output:
367159086
result:
ok single line: '367159086'
Test #45:
score: 40
Accepted
time: 2ms
memory: 4264kb
input:
71 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61 1 62 ...
output:
715534167
result:
ok single line: '715534167'
Test #46:
score: 40
Accepted
time: 7ms
memory: 4084kb
input:
79 1 2 2 3 2 4 4 5 3 6 4 7 7 8 6 9 9 10 10 11 10 12 10 13 11 14 12 15 14 16 14 17 15 18 17 19 19 20 18 21 21 22 22 23 21 24 24 25 25 26 25 27 27 28 28 29 29 30 28 31 30 32 30 33 31 34 33 35 33 36 34 37 37 38 38 39 37 40 40 41 40 42 40 43 41 44 43 45 43 46 45 47 45 48 48 49 48 50 48 51 51 52 50 53 51...
output:
192185403
result:
ok single line: '192185403'
Test #47:
score: 40
Accepted
time: 9ms
memory: 4148kb
input:
78 1 2 1 3 2 4 1 5 2 6 4 7 7 8 5 9 8 10 9 11 8 12 9 13 12 14 14 15 14 16 14 17 16 18 16 19 18 20 18 21 20 22 20 23 21 24 24 25 22 26 23 27 25 28 28 29 28 30 30 31 30 32 31 33 32 34 34 35 32 36 35 37 36 38 35 39 38 40 40 41 40 42 39 43 42 44 41 45 42 46 44 47 46 48 48 49 48 50 50 51 51 52 49 53 51 54...
output:
275960320
result:
ok single line: '275960320'
Test #48:
score: 40
Accepted
time: 8ms
memory: 4076kb
input:
78 1 2 1 3 3 4 4 5 1 6 6 7 6 8 4 9 8 10 10 11 10 12 9 13 9 14 13 15 14 16 16 17 14 18 18 19 19 20 20 21 20 22 22 23 23 24 23 25 23 26 24 27 26 28 25 29 27 30 30 31 28 32 28 33 32 34 34 35 33 36 32 37 37 38 37 39 35 40 40 41 39 42 40 43 42 44 43 45 43 46 45 47 43 48 45 49 46 50 46 51 51 52 51 53 50 5...
output:
79692172
result:
ok single line: '79692172'
Test #49:
score: 40
Accepted
time: 7ms
memory: 4004kb
input:
76 1 2 2 3 3 4 4 5 1 6 2 7 5 8 6 9 5 10 8 11 8 12 12 13 9 14 13 15 12 16 11 17 15 18 15 19 16 20 17 21 18 22 18 23 23 24 21 25 21 26 24 27 27 28 24 29 26 30 26 31 26 32 29 33 28 34 30 35 31 36 32 37 37 38 33 39 34 40 37 41 38 42 38 43 40 44 41 45 42 46 46 47 45 48 46 49 44 50 49 51 49 52 50 53 51 54...
output:
155298272
result:
ok single line: '155298272'
Test #50:
score: 40
Accepted
time: 2ms
memory: 4248kb
input:
78 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 16 33 18 34 1 35 16 36 13 37 35 38 11 39 33 40 29 41 22 42 29 43 11 44 22 45 9 46 21 47 35 48 1 49 27 50 23 51 14 52 21 53 44 54 39 55 25 56 39 57 41 ...
output:
347869842
result:
ok single line: '347869842'
Test #51:
score: 40
Accepted
time: 2ms
memory: 4284kb
input:
73 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 18 34 32 35 32 36 26 37 31 38 32 39 23 40 11 41 12 42 18 43 36 44 18 45 26 46 22 47 45 48 25 49 18 50 13 51 27 52 9 53 42 54 51 55 54 56 10 57 11...
output:
320963094
result:
ok single line: '320963094'
Test #52:
score: 40
Accepted
time: 2ms
memory: 3976kb
input:
70 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 21 35 10 36 20 37 27 38 9 39 28 40 17 41 2 42 20 43 21 44 16 45 19 46 18 47 13 48 4 49 12 50 22 51 16 52 44 53 13 54 27 55 7 56 47 57 44 58 ...
output:
203034247
result:
ok single line: '203034247'
Test #53:
score: 40
Accepted
time: 3ms
memory: 4264kb
input:
75 1 2 1 3 1 4 3 5 1 6 4 7 6 8 2 9 2 10 3 11 4 12 2 13 1 14 2 15 11 16 10 17 2 18 8 19 13 20 17 21 4 22 6 23 16 24 5 25 3 26 5 27 2 28 5 29 20 30 22 31 6 32 17 33 2 34 7 35 4 36 16 37 7 38 22 39 7 40 27 41 5 42 42 43 38 44 20 45 23 46 36 47 46 48 14 49 23 50 26 51 18 52 4 53 51 54 41 55 54 56 25 57 ...
output:
917400836
result:
ok single line: '917400836'
Test #54:
score: 40
Accepted
time: 3ms
memory: 3956kb
input:
76 1 2 1 3 2 4 1 5 4 6 3 7 6 8 8 9 1 10 3 11 3 12 4 13 11 14 3 15 5 16 6 17 17 18 3 19 13 20 6 21 4 22 16 23 22 24 5 25 11 26 8 27 17 28 8 29 15 30 30 31 25 32 20 33 11 34 8 35 33 36 27 37 29 38 5 39 8 40 4 41 31 42 32 43 27 44 1 45 39 46 39 47 43 48 35 49 44 50 9 51 10 52 26 53 5 54 25 55 17 56 12 ...
output:
716634289
result:
ok single line: '716634289'
Test #55:
score: 40
Accepted
time: 3ms
memory: 4328kb
input:
74 1 2 1 3 2 4 1 5 2 6 6 7 5 8 1 9 4 10 10 11 7 12 7 13 6 14 13 15 10 16 15 17 14 18 12 19 2 20 4 21 19 22 9 23 5 24 21 25 17 26 17 27 19 28 11 29 5 30 16 31 5 32 30 33 11 34 29 35 14 36 29 37 4 38 11 39 1 40 4 41 6 42 1 43 36 44 29 45 7 46 36 47 38 48 40 49 14 50 36 51 33 52 48 53 23 54 38 55 18 56...
output:
920487193
result:
ok single line: '920487193'
Test #56:
score: 40
Accepted
time: 0ms
memory: 4020kb
input:
70 1 2 2 3 1 4 2 5 4 6 5 7 7 8 5 9 6 10 3 11 2 12 4 13 10 14 5 15 8 16 3 17 14 18 4 19 2 20 12 21 4 22 11 23 8 24 21 25 25 26 13 27 15 28 23 29 9 30 16 31 9 32 27 33 15 34 12 35 8 36 12 37 7 38 37 39 16 40 24 41 36 42 21 43 29 44 30 45 38 46 3 47 6 48 42 49 37 50 1 51 3 52 30 53 12 54 3 55 3 56 33 5...
output:
689277044
result:
ok single line: '689277044'
Test #57:
score: 40
Accepted
time: 3ms
memory: 4060kb
input:
71 1 2 2 3 2 4 3 5 2 6 1 7 7 8 3 9 2 10 6 11 10 12 9 13 4 14 2 15 14 16 16 17 14 18 14 19 4 20 5 21 16 22 7 23 20 24 16 25 24 26 26 27 14 28 16 29 12 30 14 31 20 32 14 33 25 34 18 35 25 36 22 37 24 38 4 39 32 40 3 41 24 42 30 43 21 44 25 45 21 46 7 47 17 48 42 49 20 50 16 51 45 52 18 53 7 54 47 55 4...
output:
358090698
result:
ok single line: '358090698'
Test #58:
score: 40
Accepted
time: 3ms
memory: 4292kb
input:
73 1 2 1 3 2 4 4 5 5 6 6 7 7 8 2 9 7 10 6 11 9 12 11 13 4 14 10 15 8 16 9 17 11 18 9 19 19 20 1 21 12 22 5 23 6 24 4 25 18 26 20 27 25 28 13 29 10 30 18 31 5 32 2 33 19 34 26 35 19 36 14 37 7 38 9 39 26 40 26 41 37 42 36 43 43 44 17 45 13 46 1 47 4 48 40 49 17 50 8 51 12 52 29 53 19 54 1 55 15 56 20...
output:
959769486
result:
ok single line: '959769486'
Test #59:
score: 40
Accepted
time: 4ms
memory: 4296kb
input:
72 1 2 2 3 2 4 4 5 5 6 2 7 3 8 3 9 4 10 6 11 9 12 10 13 12 14 11 15 8 16 14 17 9 18 8 19 15 20 16 21 16 22 18 23 12 24 13 25 15 26 20 27 25 28 2 29 18 30 7 31 29 32 9 33 20 34 28 35 3 36 13 37 17 38 15 39 16 40 30 41 4 42 27 43 34 44 34 45 22 46 2 47 19 48 36 49 28 50 37 51 40 52 23 53 9 54 20 55 42...
output:
513471410
result:
ok single line: '513471410'
Test #60:
score: 40
Accepted
time: 3ms
memory: 4040kb
input:
76 1 2 1 3 3 4 1 5 1 6 3 7 5 8 4 9 8 10 1 11 4 12 10 13 6 14 8 15 3 16 10 17 9 18 10 19 4 20 8 21 11 22 7 23 2 24 10 25 16 26 25 27 13 28 2 29 28 30 15 31 16 32 23 33 14 34 33 35 31 36 8 37 31 38 36 39 14 40 15 41 14 42 15 43 4 44 39 45 42 46 24 47 34 48 40 49 31 50 33 51 15 52 41 53 43 54 45 55 48 ...
output:
632208880
result:
ok single line: '632208880'
Test #61:
score: 40
Accepted
time: 0ms
memory: 3992kb
input:
74 1 2 1 3 2 4 2 5 5 6 6 7 4 8 4 9 6 10 2 11 3 12 4 13 2 14 2 15 5 16 14 17 2 18 10 19 1 20 5 21 15 22 6 23 11 24 9 25 10 26 19 27 24 28 23 29 18 30 20 31 29 32 9 33 30 34 27 35 2 36 28 37 4 38 17 39 8 40 12 41 16 42 15 43 38 44 23 45 41 46 19 47 18 48 28 49 22 50 49 51 35 52 41 53 32 54 13 55 38 56...
output:
139851470
result:
ok single line: '139851470'
Test #62:
score: 40
Accepted
time: 2ms
memory: 4016kb
input:
73 1 2 2 3 1 4 2 5 1 6 1 7 6 8 1 9 5 10 10 11 10 12 1 13 10 14 13 15 9 16 10 17 3 18 8 19 14 20 20 21 1 22 3 23 3 24 4 25 7 26 5 27 11 28 21 29 6 30 11 31 30 32 10 33 23 34 25 35 3 36 22 37 18 38 15 39 8 40 20 41 10 42 1 43 27 44 12 45 29 46 37 47 18 48 47 49 16 50 17 51 14 52 17 53 43 54 23 55 48 5...
output:
248495359
result:
ok single line: '248495359'