QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#418332 | #3748. 买一送一 | ZayinCTT# | AC ✓ | 70ms | 18832kb | C++14 | 738b | 2024-05-23 12:47:47 | 2024-05-23 12:47:49 |
Judging History
answer
#include<iostream>
#include<vector>
using ll = long long;
int n, a[100005], c[100005], p[100005]; ll f[100005];
std::vector<int> son[100005];
void dfs(int u) {
static int C; static ll D; c[u] = C;
int x = p[a[u]]; D -= c[x];
if (!x) C++; p[a[u]] = u, D += c[u];
f[u] = D;
for (int v : son[u]) dfs(v);
if (!x) C--; D -= c[u], p[a[u]] = x, D += c[x];
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
while (std::cin >> n) {
for (int i = 2; i <= n; i++) {
int x; std::cin >> x, son[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++) son[i].clear();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 70ms
memory: 18832kb
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