QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283821 | #7677. Easy Diameter Problem | Max_s_xaM | WA | 9ms | 20996kb | C++14 | 6.2kb | 2023-12-15 15:52:19 | 2023-12-15 15:52:21 |
Judging History
answer
#include <iostream>
#include <vector>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 310, MAXM = 610, mod = 1e9 + 7;
int n;
vector <int> e[MAXN];
ll fac[MAXM], inv[MAXM];
inline ll C(int n, int m) {return (n < m || m < 0 ? 0 : fac[n] * inv[m] % mod * inv[n - m] % mod);}
inline ll Calc(int n, int m) {return (n == 0 || m < 0 ? 1 : C(n + m, m));}
int ev[MAXN][2], eid[MAXN][MAXN];
int dis[2][MAXN][MAXN], cnt[2][MAXN][MAXN];
int len, Mid;
void DFS(int u, int fa, int rt, bool d)
{
cnt[d][rt][dis[d][rt][u]]++;
for (auto v : e[u])
if (v != fa)
{
dis[d][rt][v] = dis[d][rt][u] + 1;
DFS(v, u, rt, d);
}
}
inline void Init()
{
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (int i = 2; i < MAXM; i++) fac[i] = fac[i - 1] * i % mod, inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = 2; i < MAXM; i++) inv[i] = inv[i - 1] * inv[i] % mod;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < 2; j++)
DFS(ev[i][j], ev[i][j ^ 1], i, j);
int cur = 1;
for (int j = n; j >= 0; j--)
if (cnt[0][i][j]) {cur += j; break;}
for (int j = n; j >= 0; j--)
if (cnt[1][i][j]) {cur += j; break;}
if (len < cur || (len == cur && !Mid))
{
len = cur;
if (cnt[0][i][(len - 1) / 2] && cnt[1][i][len / 2])
Mid = i;
}
}
}
int f[MAXN][2][MAXN << 1][MAXN];
int main()
{
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n);
for (int i = 1, u, v; i < n; i++)
{
Read(u), Read(v);
ev[i][0] = u, ev[i][1] = v;
eid[u][v] = eid[v][u] = i;
e[u].push_back(v), e[v].push_back(u);
}
Init();
// cout << len << " " << Mid << "\n";
// for (int i = 1; i < n; i++)
// {
// for (int j = 1; j <= n; j++) cout << dis[0][i][j] << ' ';
// cout << "\n";
// for (int j = 1; j <= n; j++) cout << dis[1][i][j] << " ";
// cout << "\n\n";
// }
for (int i = 1; i < n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < n - 1; k++)
f[i][j][1][k] = 2;
for (int r = 2; r <= len; r++)
{
for (int i = 1; i < n; i++)
for (int j = 0; j < 2; j++)
{
int u = ev[i][j], w = ev[i][j ^ 1], Eid, Vid;
int cntw, cntu;
for (int k = 0; k < n - r; k++)
{
// cout << i << " " << j << " " << r << " " << k << " #:\n";
if (r & 1)
{
cntw = cnt[j ^ 1][i][r - 1 >> 1];
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j][r - 1][k + cntw] * fac[cntw]) % mod;
cntu = cnt[j][i][r - 1 >> 1];
for (int m = 1; m <= cntu; m++)
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j ^ 1][r - 1][m] * fac[cntu] % mod * Calc(cntu - m, k - 1)) % mod;
}
else
{
cntw = cnt[j ^ 1][i][r - 2 >> 1];
for (auto v : e[u]) if (v != w)
{
Eid = eid[v][u], Vid = (ev[Eid][1] == v);
cntu = cnt[j][i][r >> 1] - cnt[Vid][Eid][r - 2 >> 1];
// cout << Eid << " " << Vid << " " << r - 1 << " " << k + cntu + cntw << "\n";
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[Eid][Vid][r - 1][k + cntu + cntw] * fac[cntw] % mod * fac[cntu] % mod * Calc(cntu, k + cntw)) % mod;
}
cntu = cnt[j][i][r >> 1];
for (int m = 1; m <= cntu; m++)
f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j ^ 1][r - 1][m] * fac[cntu] % mod * Calc(cntu - m, k - 1)) % mod;
}
}
}
}
// for (int r = 1; r <= len; r++, cout << "\n")
// for (int i = 1; i < n; i++, cout << "\n")
// for (int j = 0; j < 2; j++)
// for (int k = 0; k < n; k++) cout << f[i][j][r][k] << " ";
ll ans = 0;
if (len & 1) ans = f[Mid][0][len][0];
else ans = f[Mid][1][len][0];
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7624kb
input:
3 1 2 3 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 13656kb
input:
5 4 1 4 5 1 2 1 3
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 0ms
memory: 17808kb
input:
7 5 7 2 5 2 1 1 6 3 6 4 1
output:
116
result:
ok 1 number(s): "116"
Test #4:
score: -100
Wrong Answer
time: 9ms
memory: 20996kb
input:
100 89 60 66 37 59 74 63 49 69 37 9 44 94 22 70 30 79 14 25 33 23 4 78 43 63 30 95 7 6 59 56 31 21 56 58 43 95 28 81 19 63 40 58 87 81 38 100 55 78 23 37 78 86 70 33 11 52 17 42 19 19 13 70 100 97 79 66 67 66 27 82 55 15 27 68 33 97 26 46 20 70 93 1 10 69 79 81 45 58 95 24 63 79 51 85 11 12 43 41 64...
output:
995141791
result:
wrong answer 1st numbers differ - expected: '748786623', found: '995141791'