QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88832#5372. 杀蚂蚁简单版Scintilla0 97ms25836kbC++142.6kb2023-03-17 17:37:012023-03-17 17:37:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-17 17:37:03]
  • 评测
  • 测评结果:0
  • 用时:97ms
  • 内存:25836kb
  • [2023-03-17 17:37:01]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int P = 998244353;

const int N = 1e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }

int n, a[N], k[N], b[N], x[N], dfn[N], dn, p[N], dep[N], st[N][20];
vector <int> e[N];

void dfs0(int u, int fa) {
  dfn[u] = ++ dn, st[dfn[u]][0] = u, p[u] = fa;
  if (u == 2) k[u] = 1, b[u] = 0;
  else if (u > 2) {
    int q = mul(a[p[p[u]]], qpow(a[p[p[u]]] + a[u], P - 2)), iv = qpow(dec(1, q), P - 2);
    k[u] = mul(dec(k[p[u]], mul(q, k[p[p[u]]])), iv);
    b[u] = mul(dec(dec(b[p[u]], mul(q, b[p[p[u]]])), 1), iv);
  }
  x[u] = mul(dec(dec(b[u], b[p[u]]), 1), qpow(dec(k[p[u]], k[u]), P - 2));
  for (int v : e[u]) if (v != fa) {
    dep[v] = dep[u] + 1, dfs0(v, u);
  }
  // cout << "u, k[u], b[u], x[u] = " << u << ' ' << k[u] << ' ' << b[u] << ' ' << x[u] << endl;
}

int Min(int u, int v) {
  return dep[u] < dep[v] ? u : v;
}

int LCA(int u, int v) {
  if (u == v) return u;
  u = dfn[u], v = dfn[v];
  if (u > v) swap(u, v);
  int t = __lg(v - u);
  return p[Min(st[u + 1][t], st[v - (1 << t) + 1][t])];
}

int main() {
  n = read();
  rep(i, 1, n) a[i] = read();
  rep(i, 1, n - 1) {
    int u = read(), v = read();
    e[u].pb(v), e[v].pb(u);
  }
  dfs0(1, 0);
  rep(j, 1, 19) rep(i, 1, n - (1 << j) + 1) {
    st[i][j] = Min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  }
  for (int q = read(); q; -- q) {
    auto ask = [&](int u, int v) {
      if (u == 1) return 0;
      int lca = LCA(u, v);
      // cout << "u, v, lca = " << u << ' ' << v << ' ' << lca << endl;
      return inc(mul(k[lca], x[u]), b[lca]);
    } ;
    int s = read(), u = read(), v = read(), lca = LCA(u, v), res = 0;
    res = inc(res, inc(ask(u, s), ask(v, s)));
    res = dec(res, inc(ask(lca, s), ask(p[lca], s)));
    printf("%d\n", res);
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 5860kb

input:

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

output:

3

result:

wrong answer 1st lines differ - expected: '4', found: '3'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 97ms
memory: 25836kb

input:

100000
13643 13546 7538 2233 7731 14619 19601 8438 9556 19888 17313 1060 15168 11207 11183 16074 10758 7469 13444 9658 18326 4735 7542 13836 5863 7903 7212 14714 10416 18506 13435 14502 15271 13205 14887 18074 8353 19807 1767 19148 7343 10823 14211 66 17168 8305 1210 5436 18552 3659 886 18416 19261 ...

output:

945511877
445444586
463961236
617195216
102986704
129776727
484789584
988144777
928938142
975749437
983816511
924770936
150160212
394521836
99392055
984326661
988730298
533211997
423984827
207936943
176462435
100763154
128521063
250869128
750240601
856011657
850993259
650007918
362290111
866226530
3...

result:

wrong answer 1st lines differ - expected: '470097670', found: '945511877'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%