QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110877#6322. Forestry8BQubeWA 411ms44008kbC++203.9kb2023-06-04 15:01:092023-06-04 15:01:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-04 15:01:10]
  • 评测
  • 测评结果:WA
  • 用时:411ms
  • 内存:44008kb
  • [2023-06-04 15:01:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

const int MOD = 998244353;

void add(int &x, int val) {
    x += val;
    if (x >= MOD) x -= MOD;
}

struct Node {
    int mi, pri, sz;
    int method, sum, wsum, lazymul;
    Node *l, *r;
    Node(int k, int m = 1): mi(k), pri(rand()), sz(1), method(m), sum(m), wsum((ll)k * m % MOD), lazymul(1), l(0), r(0) {}
    void up() {
        sz = 1, sum = method, wsum = (ll)method * mi % MOD;
        if (l) {
            sz += l->sz;
            add(sum, l->sum);
            add(wsum, l->wsum);
        }
        if (r) {
            sz += r->sz;
            add(sum, r->sum);
            add(wsum, r->wsum);
        }
    }
    void down() {
        if (lazymul != 1) {
            if (l) l->give_tag(lazymul);
            if (r) r->give_tag(lazymul);
            lazymul = 1;
        }
    }
    void give_tag(int m) {
        method = (ll)method * m % MOD;
        sum = (ll)sum * m % MOD;
        wsum = (ll)wsum * m % MOD;
        lazymul = (ll)lazymul * m % MOD;
    }
} *root[300005];

Node *merge(Node *a, Node *b) {
    if (!a || !b) return a ? a : b;
    if (a->pri < b->pri) return a->down(), a->r = merge(a->r, b), a->up(), a;
    return b->down(), b->l = merge(a, b->l), b->up(), b;
}

void split(Node *o, Node *&a, Node *&b, int k) {
    if (!o) return a = b = 0, void();
    o->down();
    if (o->mi < k)
        a = o, split(o->r, a->r, b, k), a->up();
    else
        b = o, split(o->l, a, b->l, k), b->up();
}

void destruct(Node *o, vector<Node*> &vec) {
    if (!o) return;
    o->down();
    destruct(o->r, vec);
    Node *tmp = o->l;
    o->l = o->r = 0, o->up();
    vec.pb(o);
    destruct(tmp, vec);
}

int get_sum(Node *o) {
    return o ? o->sum : 0;
}

int arr[300005], subsz[300005], mxson[300005], pw2[300005], n, ans;
vector<int> G[300005];

void dfs(int u, int f) {
    subsz[u] = 1;
    for (int i : G[u]) {
        if (i == f) continue;
        dfs(i, u);
        if (!mxson[u] || subsz[mxson[u]] < subsz[i])
            mxson[u] = i;
        subsz[u] += subsz[i];
    }
}

void dfs2(int u, int f) {
    if (!mxson[u]) {
        root[u] = new Node(arr[u]);
        add(ans, (ll)arr[u] * pw2[n - 2] % MOD);
        return;
    }
    {
        dfs2(mxson[u], u);
        Node *a, *b;
        split(root[mxson[u]], a, b, arr[u]);
        int bsum = get_sum(b);
        add(bsum, pw2[subsz[mxson[u]] - 1]);
        root[u] = merge(a, new Node(arr[u], bsum));
    }
    for (int i : G[u])
        if (i != f && i != mxson[u]) {
            dfs2(i, u);
            vector<Node*> vec;
            destruct(root[i], vec);
            int gmul = pw2[subsz[i] - 1], rsum = 0;
            Node *tmp = 0;
            for (auto nd : vec) {
                Node *a;
                split(root[u], root[u], a, nd->mi);
                if (a) { 
                    a->give_tag(gmul);
                    add(rsum, a->sum);
                }
                add(gmul, nd->sum);
                nd->give_tag(rsum);
                tmp = merge(a, tmp);
                tmp = merge(nd, tmp);
            }
            if (root[u]) root[u]->give_tag(gmul);
            root[u] = merge(root[u], tmp);
        }
    add(ans, (ll)root[u]->wsum * pw2[n - 1 - subsz[u] + (u == f)] % MOD);
}

int main() {
    srand(time(NULL));
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    pw2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pw2[i] = pw2[i - 1];
        add(pw2[i], pw2[i - 1]);
    }
    for (int i = 1; i <= n; ++i)
        cin >> arr[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1, 1);
    dfs2(1, 1);
    cout << ans << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 17160kb

input:

4
1 2 3 4
1 2
2 4
3 2

output:

44

result:

ok 1 number(s): "44"

Test #2:

score: 0
Accepted
time: 0ms
memory: 17128kb

input:

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

output:

154

result:

ok 1 number(s): "154"

Test #3:

score: -100
Wrong Answer
time: 411ms
memory: 44008kb

input:

278989
864394090 384799247 186936242 598547507 962916136 540758021 158527118 688236322 682301622 948660645 881768181 481432818 557201870 794956026 205262301 920739629 141926922 990361777 818811172 150579096 1032726 328924563 638044961 21740781 484574329 737977343 113738003 345289940 363021157 582495...

output:

245225638

result:

wrong answer 1st numbers differ - expected: '434293031', found: '245225638'