QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#915564#3748. 买一送一Horcruxs#AC ✓71ms18688kbC++261.1kb2025-02-26 13:00:402025-02-26 13:00:41

Judging History

This is the latest submission verdict.

  • [2025-02-26 13:00:41]
  • Judged
  • Verdict: AC
  • Time: 71ms
  • Memory: 18688kb
  • [2025-02-26 13:00:40]
  • Submitted

answer

#include <bits/stdc++.h>

using i64 = long long;

int n;
std::vector <int> a(100005), c(100005), p(100005);
std::vector <i64> f(100005);
std::vector <int> s[100005];

void dfs(int u) {
    static int C;
    static i64 D;
    c[u] = C;

    int x = p[a[u]];
    D -= c[x];
    if(x == 0) {
        C++;
    }

    p[a[u]] = u;
    D += c[u];
    f[u] = D;

    for(int v : s[u]) {
        dfs(v);
    }

    if(x == 0) {
        C--;
    }
    D -= c[u];
    p[a[u]] = x;
    D += c[x];
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    while(std::cin >> n) {
        
        for(int i = 2; i <= n; i++) {
            int x;
            std::cin >> x;
            s[x].push_back(i);
        }

        for(int i = 1; i <= n; i++) {
            std::cin >> a[i];
        }

        dfs(1);

        for(int i = 2; i <= n; i++) {
            std::cout << f[i] << '\n';
        }

        for(int i = 1; i <= n; i++) {
            s[i].clear();
        }
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 71ms
memory: 18688kb

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