QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397442#3748. 买一送一SamponYWAC ✓87ms19948kbC++141.9kb2024-04-24 08:49:552024-04-24 08:49:55

Judging History

This is the latest submission verdict.

  • [2024-04-24 08:49:55]
  • Judged
  • Verdict: AC
  • Time: 87ms
  • Memory: 19948kb
  • [2024-04-24 08:49:55]
  • Submitted

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 100005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int n, a[N]; vector<int> e[N];
ll ans[N]; int v[N], pre[N], s[N], mu[N];
il void upd(int x, int v) {while(x <= n) s[x] += v, x += x & -x;}
il int query(int x) {int v = 0; while(x) v += s[x], x ^= x & -x; return v;}
il int query(int l, int r) {return query(r) - query(l - 1);}
il void dfs(int x, int d = 1) {
  int s = pre[a[x]]; pre[a[x]] = d;
  ans[x] = query(s + 1, d); int p = mu[a[x]];
  if(s > 0) ans[x] += !mu[a[x]], mu[a[x]] = 1;
  if(!v[a[x]]++) upd(d, 1);
  for(auto y : e[x]) dfs(y, d + 1);
  if(!--v[a[x]]) upd(d, -1);
  pre[a[x]] = s, mu[a[x]] = p;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while(cin >> n) {
    FOR(x, 1, n) vector<int>().swap(e[x]);
    FOR(x, 2, n) {int f; cin >> f, e[f].eb(x);}
    FOR(x, 1, n) cin >> a[x]; dfs(1);
    FOR(x, 1, n) for(auto y : e[x]) ans[y] += ans[x];
    FOR(x, 2, n) cout << ans[x] << "\n";
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC;
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 87ms
memory: 19948kb

input:

100
1 2 3 4 5 5 7 7 9 10 11 12 13 13 15 13 12 18 12 11 10 7 7 4 25 26 27 4 2 30 31 32 33 34 34 36 34 33 33 33 32 32 30 2 45 1 47 48 49 50 51 52 53 52 55 56 56 52 59 60 59 59 63 64 51 66 49 68 69 68 47 72 73 72 75 76 77 78 79 80 80 82 77 84 77 86 76 88 75 72 91 92 72 94 94 96 97 94 72
55 12 85 53 40 ...

output:

1
3
6
10
15
15
21
21
28
30
38
47
57
57
68
55
47
57
47
38
36
21
21
10
15
21
28
10
3
6
10
15
21
28
28
36
28
21
21
21
15
15
6
3
6
1
3
6
10
15
21
28
36
28
36
45
45
28
36
45
30
36
45
55
21
28
10
15
17
15
3
6
10
6
10
15
21
28
36
45
45
55
21
28
21
28
15
21
10
6
10
15
6
10
10
15
21
10
6
1
3
6
6
10
15
21
28
...

result:

ok 498996 numbers