QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110877 | #6322. Forestry | 8BQube | WA | 411ms | 44008kb | C++20 | 3.9kb | 2023-06-04 15:01:09 | 2023-06-04 15:01:10 |
Judging History
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'