QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693388#9530. A Game On TreexorzjWA 210ms20964kbC++177.2kb2024-10-31 16:03:502024-10-31 16:03:56

Judging History

This is the latest submission verdict.

  • [2024-10-31 16:03:56]
  • Judged
  • Verdict: WA
  • Time: 210ms
  • Memory: 20964kb
Show
  • [2024-10-31 16:03:50]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(a, b, c) for (int a = b; a <= c; a++)
#define ALL(x) (x).begin(), (x).end()
#define IOS cin.tie(0)->sync_with_stdio(false)
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) 42
#endif
#define OPENSTACK
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
template <class T>
constexpr T qpow(T a, ll b)
{
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr ll mul(ll a, ll b, ll p)
{
    ll res = a * b - ll(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template <ll P>
struct MLong {
    ll x;
    constexpr MLong() : x{} {}
    constexpr MLong(ll x) : x{ norm(x % getMod()) } {}

    static ll Mod;
    constexpr static ll getMod()
    {
        if (P > 0) {
            return P;
        }
        else {
            return Mod;
        }
    }
    constexpr static void setMod(ll Mod_) { Mod = Mod_; }
    constexpr ll norm(ll x) const
    {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr ll val() const { return x; }
    explicit constexpr operator ll() const { return x; }
    constexpr MLong operator-() const
    {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const
    {
        assert(x != 0);
        return qpow(*this, getMod() - 2);
    }
    constexpr MLong& operator*=(MLong rhs)&
    {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong& operator+=(MLong rhs)&
    {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong& operator-=(MLong rhs)&
    {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong& operator/=(MLong rhs)& { return *this *= rhs.inv(); }
    friend constexpr MLong operator*(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream& operator>>(std::istream& is, MLong& a)
    {
        ll v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const MLong& a)
    {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs)
    {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs)
    {
        return lhs.val() != rhs.val();
    }
};

template <>
ll MLong<0LL>::Mod = ll(1E18) + 9;

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(ll x) : x{ norm(x % getMod()) } {}

    static int Mod;
    constexpr static int getMod()
    {
        if (P > 0) {
            return P;
        }
        else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) { Mod = Mod_; }
    constexpr int norm(int x) const
    {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }
    constexpr MInt operator-() const
    {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const
    {
        assert(x != 0);
        return qpow(*this, getMod() - 2);
    }
    constexpr MInt& operator*=(MInt rhs)&
    {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt& operator+=(MInt rhs)&
    {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt& operator-=(MInt rhs)&
    {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt& operator/=(MInt rhs)& { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream& operator>>(std::istream& is, MInt& a)
    {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const MInt& a)
    {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs)
    {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs)
    {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>>adj(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    vector<int>siz(n + 1);
    vector<Z>sum(n + 1);
    Z ans = 0;
    auto dfs = [&](int x, int fa, auto self)->void {
        siz[x] = 1;
        for (auto y : adj[x]) {
            if (y == fa)continue;
            self(y, x, self);
            siz[x] += siz[y];
            sum[x] += sum[y];
        }
        // cerr << x << " " << siz[x] << " " << sum[x] << " " << ans << "\n";
        for (auto y : adj[x]) {
            if (y == fa)continue;
            ans += (sum[x] - sum[y]) * sum[y];
            ans += Z(2) * (n - siz[y]) * (n - siz[y]) * (sum[y] - 1LL * (siz[y] * siz[y]));
            ans += Z(n - siz[y]) * siz[y] * siz[y] * (n - siz[y]);
        }
        sum[x] += 1LL * siz[x] * siz[x];
        // cerr << ans << "\n";
    };
    dfs(1, 0, dfs);
    // cout << ans << "\n";
    Z p = Z(n) * (n - 1) * n * (n - 1) / 4;
    cout << ans / p << "\n";
}
int main()
{
#ifdef LOCAL
#ifdef OPENSTACK
    int size = 128 << 20; // 64MB
    char* p = (char*) malloc(size) + size;
#if (defined _WIN64) or (defined __unix)
    __asm__("movq %0, %%rsp\n" ::"r"(p));
#else
    __asm__("movl %0, %%esp\n" ::"r"(p));
#endif
#endif
#endif
    IOS;
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
#ifdef LOCAL
#ifdef OPENSTACK
    exit(0);
#else
    return 0;
#endif
#endif
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

input:

2
3
1 2
2 3
5
1 2
1 5
3 2
4 2

output:

443664158
918384806

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

1000
7
3 6
4 3
5 3
2 6
1 4
7 1
12
5 7
10 7
2 10
11 2
1 7
8 1
4 2
9 11
6 9
12 11
3 5
6
2 5
1 2
4 5
6 4
3 6
5
2 5
1 5
4 5
3 2
8
1 8
2 8
4 2
6 1
5 6
7 6
3 8
8
3 8
7 3
4 8
6 4
2 7
5 2
1 4
4
3 1
4 3
2 1
6
5 1
6 1
2 5
3 5
4 2
12
8 11
5 11
12 8
3 12
6 12
2 3
4 6
10 11
1 5
9 5
7 5
9
6 1
7 6
4 7
8 7
5 4
9 6
...

output:

948445317
468414020
550143557
918384806
711758412
487662742
776412276
869581749
240852807
765628773
211048577
887328316
890334966
940494682
760637552
908032643
592850815
584006902
908525604
221832080
433351719
56023919
867301808
183319566
698771049
366957926
449579681
599710576
310564911
286902823
3...

result:

ok 1000 lines

Test #3:

score: 0
Accepted
time: 17ms
memory: 3580kb

input:

1000
94
59 1
33 59
73 1
6 33
83 59
4 59
20 59
61 6
39 1
76 73
71 6
44 39
9 71
24 4
87 9
57 83
2 9
81 71
82 20
90 2
85 39
12 9
30 83
66 30
53 9
47 9
36 44
43 53
29 12
31 53
64 81
38 31
84 82
77 38
23 71
93 84
78 83
58 31
68 90
42 1
55 64
13 78
70 78
62 24
19 55
92 87
14 57
10 84
65 81
63 6
75 36
91 1...

output:

508107725
996793960
201633249
335988372
842755864
460619380
342223697
207523414
429241811
391691799
542977964
786416604
454278948
685531402
25914978
440729774
228518323
679471537
82764520
554190841
432505337
143444089
189106586
337234245
61954935
905141094
532919674
703954588
185671863
942858630
692...

result:

ok 1000 lines

Test #4:

score: -100
Wrong Answer
time: 210ms
memory: 20964kb

input:

10000
8
1 4
3 1
5 1
7 3
8 4
6 8
2 7
8
2 6
4 6
5 6
8 5
7 6
3 5
1 7
8
8 5
6 5
2 5
7 2
1 6
3 1
4 8
9
8 6
9 8
3 6
1 8
5 9
2 8
4 3
7 9
8
8 6
3 6
5 8
1 6
4 3
7 6
2 6
9
9 5
7 5
2 7
8 7
4 9
3 7
6 3
1 4
8
1 4
5 1
6 5
3 4
8 4
7 8
2 5
9
1 8
6 1
2 1
3 8
5 3
9 8
7 8
4 8
9
4 9
2 9
1 2
3 4
5 2
6 9
8 3
7 2
8
1 2
8 ...

output:

49657566
56023919
387074343
97051536
701572244
211048577
711758412
308100110
761007271
711758412
178698065
285212675
80216065
43380497
267677376
818005792
53239701
765628773
970145625
387074343
436731906
422725927
479157293
977872021
436731906
925779210
487662742
705549251
267677376
711758412
526851...

result:

wrong answer 9992nd lines differ - expected: '391800050', found: '542995636'
English 繁體中文 简体中文

Server Time: 2025-02-09 05:05:33 | OpenSource Project