QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283821#7677. Easy Diameter ProblemMax_s_xaMWA 9ms20996kbC++146.2kb2023-12-15 15:52:192023-12-15 15:52:21

Judging History

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

  • [2023-12-15 15:52:21]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:20996kb
  • [2023-12-15 15:52:19]
  • 提交

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'